Leetcode刷题之旅(每日一题)--215. 数组中的第K个最大元素

题目描述：

思路：第一种想法就是直接排序然后得到第K大的数字。

class Solution {
    public int findKthLargest(int[] nums, int k) {
        int n=nums.length;
        int[] num=quicksort(nums,0,n-1);
        return num[n-k];
    }


    private int[] quicksort(int[] num,int left,int right){
        int i=left;
        int j=right;
        int temp=num[left];
        while(j>i){
            while(j>i&&num[j]>=temp){
                j--;
            }
            num[i]=num[j];
            while(j>i&&num[i]<=temp){
                i++;
            }
            num[j]=num[i];
        }
        num[j]=temp;
        if (i-1>left) num=quicksort(num,left,i-1);
        if (j+1<right) num=quicksort(num,j+1,right);
        return num;
    }
}
           

先用快速排序得到排序之后得到结果。结果确实是正确的，但是

怎么样能够改进呢？看了下官方解答，对快速排序进行了优化。由于我们只要第K大的数字，而整个数组是否有序并不重要。因此当快速排序过程中当枢纽值的下标正好是第n-k时(n为数组长度)，那么就已经得到了第K大的元素，再继续往下排序是不需要的。依据这种想法可以很大的改善时间复杂度。

这种想法的代码(官方的代码)

class Solution {
    Random random = new Random();

    public int findKthLargest(int[] nums, int k) {
        return quickSelect(nums, 0, nums.length - 1, nums.length - k);
    }

    public int quickSelect(int[] a, int l, int r, int index) {
        int q = randomPartition(a, l, r);
        if (q == index) {
            return a[q];
        } else {
            return q < index ? quickSelect(a, q + 1, r, index) : quickSelect(a, l, q - 1, index);
        }
    }

    public int randomPartition(int[] a, int l, int r) {
        int i = random.nextInt(r - l + 1) + l;
        swap(a, i, r);
        return partition(a, l, r);
    }

    public int partition(int[] a, int l, int r) {
        int x = a[r], i = l - 1;
        for (int j = l; j < r; ++j) {
            if (a[j] <= x) {
                swap(a, ++i, j);
            }
        }
        swap(a, i + 1, r);
        return i + 1;
    }

    public void swap(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}
           

其中官方选择枢纽值用的是随机选择。

这种想法极大的优化了时间复杂度。但是看了leetcode的解题视频，其中说明了这种做法只能处理静态的、已知的数据，而不能处理动态的。仔细想了想，没错一旦数据是动态的，快速排序算法也将不再适用，那么这种根据快速排序算法改进得来的快速选择算法也将失效。那么如果是动态数据该怎么做呢？答案是用堆排序改进的选择算法。

(官方代码)

class Solution {
    public int findKthLargest(int[] nums, int k) {
        int heapSize = nums.length;
        buildMaxHeap(nums, heapSize);
        for (int i = nums.length - 1; i >= nums.length - k + 1; --i) {
            swap(nums, 0, i);
            --heapSize;
            maxHeapify(nums, 0, heapSize);
        }
        return nums[0];
    }

    public void buildMaxHeap(int[] a, int heapSize) {
        for (int i = heapSize / 2; i >= 0; --i) {
            maxHeapify(a, i, heapSize);
        }
    }

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

    public void swap(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}
           

不低于快速排序选择算法。