讨论/《排序算法全解析》 - 215. 数组中的第 K 个最大元素/
《排序算法全解析》 - 215. 数组中的第 K 个最大元素
class Solution {
    public int findKthLargest(int[] nums, int k) {
        int kk = nums.length - k;
        buildMaxHeap(nums);
        for (int i = nums.length - 1; i >= kk; i--) {
            swap(nums, 0, i);
            maxHeapify(nums, 0, i);
        }
        return nums[kk];
    }

    private void buildMaxHeap(int[] nums) {
        for (int i = ((nums.length >> 1) - 1); i >= 0; i--) {
            maxHeapify(nums, i, nums.length);
        }
    }

    private void maxHeapify(int[] nums,int i,int heapSize) {
        int l = (i << 1) + 1;
        int r = l + 1;
        int largest = i;
        if (l < heapSize && nums[l] > nums[largest]) {
            largest = l;
        }
        if (r < heapSize && nums[r] > nums[largest]) {
            largest = r;
        }
        if (largest != i) {
            swap(nums, i, largest);
            maxHeapify(nums, largest, heapSize);
        }
    }

    private void swap(int[] nums,int i,int j) {
        if (nums[i] == nums[j]) {
            return;
        }
        nums[i] = nums[i] ^ nums[j];
        nums[j] = nums[i] ^ nums[j];
        nums[i] = nums[i] ^ nums[j];
    }
}
展开全部 2 讨论