LeetCode 215. Kth Largest Element in an Array

[Woodyiiiiiii]

Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

Example 1:

Input: [3,2,1,5,6,4] and k = 2
Output: 5

Example 2:

Input: [3,2,3,1,2,4,5,5,6] and k = 4
Output: 4

Note:
You may assume k is always valid, 1 ≤ k ≤ array's length.

---

这题如果用编程语言(C++, Java等)自带的排序库函数的话，直接可以找到k th的数：

class Solution {
    public int findKthLargest(int[] nums, int k) {
        Arrays.sort(nums);
        return nums[nums.length - k];
    }
}

Java自带的Arrays.sort函数实现是两种排序方法，相关知识如下：

Arrays.sort使用了两种排序方法，quick sort 和优化的 merge sort。
quick sort 主要是对哪些基本类型数据（int, short, long, float, double等）排序， 而 merge sort 用于对对象类型进行排序。

quick sort 在统计意义上效率比 merge sort 高，为何不都采用 quick sort ?
概括的说，一个是稳定性，一个是移动次数。'
使用不同类型的排序算法主要是由于 quick sort 是不稳定的，而 merge sort 是 stable 的。
这里的 stable 是指比较相等的数据在排序之后仍然按照排序之前的前后顺序排列（保序性）。
对于基本数据类型，稳定性没有意义。而对于对象类型，稳定性是比较重要的，因为对象相等的判断可能只是判断关键属性，最好保持相等对象的非关键属性的顺序与排序前一致；
另外一个原因是由于合并排序相对而言比较次数比快速排序少，移动（对象引用的移动）次数比快速排序多，而对于对象来说，比较一般比移动耗时。

快排平均时间复杂度是O(nlgn)，不稳定时是O(n^2)；归并排序平均时间复杂度是O(nlgn)，不稳定时也是O(nlgn)。

当然这显然不合题意的，题目原意是利用快排中切分的思想——当完成一次切分时，轴数据在数组中的位置是确定的，即如果一次切分后轴数据位置是k-1，则就是题目答案，直接返回；如果小于k-1，则将左边界设为pivot+1；反之。自己根据以前学的快排算法如下：

class Solution {
    public int findKthLargest(int[] nums, int k) {
        int lo = 0, hi = nums.length - 1;
        if (hi == 0) {
            return nums[0];
        }
        while (true) {
            int pivot = partition(nums, lo, hi);
            if (pivot == k - 1) return nums[pivot];
            else if (pivot > k - 1) hi = pivot - 1;
            else lo = pivot + 1;
            if (lo >= hi) {
                return nums[lo];
            }
        }
    }
    // 切分
    int partition(int[] nums, int lo, int hi) {
        int i = lo, j = hi + 1;
        int pivot = nums[lo];
        while (true) {
            while (nums[++i] >= pivot) if (i == hi) break;
            while (nums[--j] <= pivot) if (j == lo) break;
            if (i >= j) break;
            nums[i] ^= nums[j];
            nums[j] ^= nums[i];
            nums[i] ^= nums[j];
        }
        if (lo != j) {
            nums[lo] ^= nums[j];
            nums[j] ^= nums[lo];
            nums[lo] ^= nums[j];
        }
        return j;
    }
}

这段代码太冗长了，首先交换数据使用异或，如果数据是相同的但不为0，那么异或后的结果是0，跟交换的原意违背，这种情况很可能在快排中出现；其次，这种写法要在while循环中判断i, j的位置，很多余但又必须。
可以看看其他大神的写法：

class Solution {
    public int findKthLargest(int[] nums, int k) {
        int lo = 0, hi = nums.length - 1;
        while (true) {
            int pos = partition(nums, lo, hi);
            if (pos == k - 1) return nums[pos];
            else if (pos > k - 1) hi = pos - 1;
            else lo = pos + 1;
        }
    }
    // 切分
    int partition(int[] nums, int lo, int hi) {
        int i = lo + 1, j = hi;
        int pivot = nums[lo];
        while (i <= j) {
            if (nums[i] < pivot && nums[j] > pivot) {
                swap(nums, i++, j--);
            }
            if (nums[i] >= pivot) ++i;
            if (nums[j] <= pivot) --j;
        }
        swap(nums, lo, j);
        return j;
    }
    // 交换
    void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

虽然运行时间比我写的解法要长，但更清晰。

同样，我们可以使用优先队列PriorityQueue实现排序，定义一个比较器将队列从大到小排序，然后一一弹出，获得理想值。

class Solution {
    public int findKthLargest(int[] nums, int k) {
        Comparator<Integer> comparator = new Comparator<Integer>() {
            @Override
            public int compare(Integer i1, Integer i2) {
                return (i2 - i1);
            }
        };
        PriorityQueue<Integer> queue = new PriorityQueue<Integer>(comparator);
        for (int num : nums) queue.add(num);
        int cnt = 0;
        while (true) {
            ++cnt;
            if (cnt == k) {
                return queue.poll();
            }
            queue.poll();
        }
    }
}

---

参考资料:

• LeetCode原题
• https://www.cnblogs.com/phoebe815/p/4249340.html
• [LeetCode] 215. Kth Largest Element in an Array grandyang/leetcode#215
• https://www.jianshu.com/p/c577796e537a