echo

任生命穿梭 时间的角落

0%

数组中的第K个最大元素

Posted on In Valine:

215. 数组中的第K个最大元素

在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

示例 1:

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

示例 2:

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

说明:

你可以假设 k 总是有效的，且 1 ≤ k ≤ 数组的长度。

遇到这题我们首先就想到直接排序：

1
2
3
4
5
6
class Solution {
    public int findKthLargest(int[] nums, int k) {
        Arrays.sort(nums);
        return nums[nums.length - k];
    }
}

我们思考快排每次都将一个元素归位，我们需要的是 nums.length - k 处的元素，我们可以改进快排，并不是需要将所有元素都排序。我们使用 partition 函数将一个元素归位，得到这个归位后的元素下标 x ，对于下标 x ，我们有三种情况：

  1. x == nums.length - k ，直接返回 nums[x]
  2. x > nums.length - k，在 x 左侧寻找，直到 x == nums.length - k
  3. x < nums.length - k，在 x 右侧寻找，直到 x == nums.length - k
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution {
    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 = partition(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 partition(int[] a, int l, int r){
        //选取基准点
        int pivot = a[l];
        int i = l, j = r;
        //使基准点左侧元素全部小于基准点，右侧元素全部大于基准点
        while(i < j){
            
            while(a[j] >= pivot && i < j){
                j--;
            }
            while(a[i] <= pivot && i < j){
                i++;
            }
            if(i < j){
                swap(a, i, j);
            }
        }
        //使基准点归位
    	swap(a, l, j);
        //返回基准点下标
    	return j;
    }

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

时间复杂度O(n)，空间复杂度O(logN)，递归栈空间。

其实所有每趟循环都将一个元素归位的算法都能解决这个问题（e.g. 冒泡排序，选择排序序，堆排序等）。出于时间复杂度的考虑，我们可以选择快速排序，堆排序，下面是堆排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
    public int findKthLargest(int[] nums, int k) {
        //建立大根堆，从最后一个非叶子结点开始向下调整
        for(int i = nums.length / 2 - 1; i >= 0; i--){
            adjustdown(nums, i, nums.length);
        }
		//类似堆排序，每次将最大值放到末尾
        for(int j = nums.length - 1; j >= nums.length - k; j--){
            swap(nums, 0, j);
            adjustdown(nums, 0, j);
        }
        return nums[nums.length - k];
    }
    
    //将 a[i] 向下调整
    public void adjustdown(int[] a, int i, int length){
        int temp = a[i];
		//选择 a[i] 左右子树中最大的子树
        for(int k = 2*i+1; k < length; k = k*2+1){
            if(k + 1 < length && a[k] < a[k + 1]){
                k++;
            }
			//如果最大的子树值 大于 根结点，根结点下调
            if(a[k] > temp){
                a[i] = a[k];
                i = k;
            }else{//根结点值大于子结点，退出递归
                break;
            }
        }
		//将调整后的结点赋值
        a[i] = temp;
    }

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

时间复杂度 O(n log n)，建堆时间代价是 O(n)，删除的总代价是 O(k log n)，因为 k < n，故渐进时间复杂度为O(n + k log n) = O(n log n)。

空间复杂度O(log n)，递归使用栈空间的空间代价。