Leetcode 215 Kth Largest Element in an Array - java 算法实现

原题：

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.
For example,
Given [3,2,1,5,6,4] and k = 2, return 5.

解题：

看到题目第一反应是采用堆排序，但是题目中只要求返回第k大的数，比K大的数的顺序不用管，因此，想到采用快速选择的方式。
快速选择与快速排序思想相同，重点是分治。

思路：

1、遍历：选取target，将比target大的元素放置在其右边，比target小的元素放置到其左边。
2、target的位置 === k 返回
3、target> k 说明说明第k大数在target的左边
4、target< k 说明第k大数在target右边

代码：

class Solution {
    public int findKthLargest(int[] nums, int k) {
        return findKthLargest2(nums, k ,0, nums.length - 1);
    }
    public int findKthLargest2(int[] nums, int k, int start ,int end) {
        int flag = nums[start];
        int left = start;
        int right = end;
        while(left < right){
            while(left < right && nums[right] <= flag){
                right --;
            }
            nums[left] = nums[right];
            while (left < right && nums[left] >= flag){
                left ++;
            }
            nums[right] = nums[left];
        }
        nums[right] = flag;
        if(left == k ){
            return nums[left];
        }
        else if(left > k){
            return findKthLargest2(nums, k, start, left - 1);
        }
        else {
            return findKthLargest2(nums, k - left - 1, left + 1, end);
        }
    }
}

注意：

临界点的选择。

总结：

虽然快速选择的关键思想是分治，但是，在解答过程中，干扰我比较长时间的是左右两个指针挖坑、填坑的过程。
快速排序的挖坑、填坑的过程如下：
定义两个指针指向数组的前后两端，并选取target，将target所在位置定义为第一个坑位；如果从右边开始的数据元素小于target，该元素进入坑位，从而形成新的坑位；接着从左边开始遍历，如果左侧元素大于target，那么该元素进入上一次形成的坑位，进而产生更新的坑位，以此规律遍历，直到左右两指针相遇。最后，target元素进入最后产生的坑位中；以此结束了选择，保证了target左边的元素都是比target小的，而右边元素都是比target大的。

最后编辑于：2018.01.15 19:30:53