215. Kth Largest Element in an Array

题目描述:

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

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

题目翻译

找出未排序数组中第k大的元素,注意,第k大是指在排序的顺序的第k大,而非距离第k大的元素。

示例1:

输入:[3,2,1,5,6,4] 以及 k = 2
输出: 5

注意: 你可以假设k永远是有效的,即1 ≤ k ≤ 数组长度

解题方案

标签: Divide and Conquer

思路:

  • 这道题有很多解法,利用分治的想法我们的思路如下:
  • 随机取输入数组中的一个数x(如数组正中间的数),遍历数组,将数组中比它小的放入左,比它大的放入右边,记两边的长度为len1与len2
  • 若k<len1,则第k大的数肯定在左边,反之在右边。
  • 在确定的范围内重复上述操作,当k = len1时,找到第k大的数。

代码:

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

    private int quickSelect(int[] arr, int k, int left, int right){
        int pivot = arr[(left + right) / 2];
        int orgL = left, orgR = right;
        while(left <= right){
            // 从右向左找到第一个小于枢纽值的数
            while(arr[left] > pivot){
                left ++;
            }
            // 从左向右找到第一个大于枢纽值的数
            while(arr[right] < pivot){
                right --;
            }
            // 将两个数互换
            if(left <= right){
                swap(arr, left, right);
                left ++;
                right --;
            }
        }
        // 最后退出的情况应该是右指针在左指针左边一格
        // 这时如果右指针还大于等于k,说明kth在左半边
        if(orgL < right && k <= right) return quickSelect(arr, k, orgL, right);
        // 这时如果左指针还小于等于k,说明kth在右半边
        if(left < orgR && k >= left) return quickSelect(arr, k, left, orgR);
        return arr[k];

    }

    private void swap(int[] arr, int idx1, int idx2){
        int tmp = arr[idx1] + arr[idx2];
        arr[idx1] = tmp - arr[idx1];
        arr[idx2] = tmp - arr[idx2];

    }
}

参考资料

results matching ""

    No results matching ""