讨论/《排序算法全解析》 - 215. 数组中的第 K 个最大元素/
《排序算法全解析》 - 215. 数组中的第 K 个最大元素
共 2 个回复
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];
    }
}
class Solution {
public:
    void heapSort(vector<int>&nums){
        initHeap(nums);
        int i=nums.size()-1;
        while(i){
            swap(nums[0],nums[i]);
            maintainHeap(nums,0,--i);
        }
    }
    void initHeap(vector<int>&nums){
        int start = nums.size()/2 - 1;
        for(int i = start;i>=0;i--){
            maintainHeap(nums,i, nums.size()-1);
        }
        return;
    }
    void maintainHeap(vector<int>&nums, int start, int end){
        int left = start*2 + 1;
        int right = left + 1;
        int largest = start;
        if(right <= end && nums[right]>nums[largest]){
            largest = right;
        }
        if(left <= end && nums[left]>nums[largest]){
            largest = left;
        }
        if(largest!=start){
            swap(nums[largest], nums[start]);
            maintainHeap(nums, largest, end);
        }
        return;
    }
    int findKthLargest(vector<int>& nums, int k) {
        heapSort(nums);
        return nums[nums.size()-k];
    }
};