classSolution { publicintfindKthLargest(int[] nums, int k) { Queue<Integer> minHeap = newPriorityQueue<>(); // 小顶堆,小于堆顶的都被过滤了,剩下的就是 topK for (inti=0; i < k; i++) { minHeap.offer(nums[i]); }
for (inti= k; i < nums.length; i++) { if (nums[i] > minHeap.peek()) { // if 判断不要亦可,具有该判断时性能更优,即只将比堆顶数值更大的数值入堆 minHeap.offer(nums[i]); minHeap.poll(); } }
classSolution { publicintfindKthLargest(int[] nums, int k) { inttargetIndex= k - 1;
intleft=0, right = nums.length - 1; while (true) { intpivotIndex= partition(nums, left, right); if (pivotIndex < targetIndex) { left = pivotIndex + 1; } elseif (pivotIndex > targetIndex) { right = pivotIndex - 1; } else { return nums[pivotIndex]; } } }
privateintpartition(int[] nums, int left, int right) { // 随机选择一个元素交换至最左侧,性能优化使用,亦可不交换 intrandomIndex= left + ThreadLocalRandom.current().nextInt(right - left + 1); swap(nums, left, randomIndex);
intpivotValue= nums[left]; intendIndex= left; // 指向左边界(含)元素 for (inti= left + 1; i <= right; i++) { if (nums[i] >= pivotValue) { swap(nums, i, ++endIndex); } } // nums[left + 1, ... endIndex] >= nums[left] swap(nums, left, endIndex); return endIndex; }
privatevoidswap(int[] nums, int i, int j) { inttmp= nums[i]; nums[i] = nums[j]; nums[j] = tmp; } }
classSolution { publicintfindKthLargest(int[] nums, int k) { inttargetIndex= k - 1;
// sort to descending
intleft=0, right = nums.length - 1; while (true) { intpivotIndex= partition(nums, left, right); if (pivotIndex < targetIndex) { left = pivotIndex + 1; } elseif (pivotIndex > targetIndex) { right = pivotIndex - 1; } else { return nums[pivotIndex]; } } }
privateintpartition(int[] nums, int left, int right) { intrandomIndex= left + ThreadLocalRandom.current().nextInt(right - left + 1); swap(nums, left, randomIndex);
intpivotValue= nums[left]; inti= left, j = right; while (i < j) { while (i < j && nums[j] <= pivotValue) { j--; } while (i < j && nums[i] >= pivotValue) { i++; } swap(nums, i, j); }
swap(nums, left, i); return i; }
privatevoidswap(int[] nums, int i, int j) { inttmp= nums[i]; nums[i] = nums[j]; nums[j] = tmp; } }