LeetCode: 215. Kth Largest Element in an Array

友情支持

如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜

支付宝

有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。

wx jikerizhi

公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。

215. Kth Largest Element in an Array

LeetCode - Kth Largest Element in an Array

Find the *k*th 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.

思路分析

没想到竟然可以使用快排的套路来解决这个问题。

一刷
二刷
三刷

 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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
private int[] nums;

private void swap(int a, int b) {
    int temp = this.nums[a];
    this.nums[a] = this.nums[b];
    this.nums[b] = temp;
}

private int partition(int left, int right, int pivotIndex) {
    int pivot = this.nums[pivotIndex];
    // 1. move pivot to end
    swap(pivotIndex, right);
    int storeIdex = left;

    // 2. move all smaller elements to the left
    for (int i = left; i < right; i++) {
        if (this.nums[i] < pivot) {
            swap(storeIdex, i);
            storeIdex++;
        }
    }
    // 3. move pivot to its final place
    swap(storeIdex, right);
    return storeIdex;
}

private int quickselect(int left, int right, int kSmallest) {
    if (left == right) {
        return this.nums[left];
    }
    Random random = new Random();
    int pivotIndex = left + random.nextInt(right - left);

    pivotIndex = partition(left, right, pivotIndex);
    if (pivotIndex == kSmallest) {
        return this.nums[kSmallest];
    } else if (kSmallest < pivotIndex) {
        return quickselect(left, pivotIndex - 1, kSmallest);
    } else {
        return quickselect(pivotIndex + 1, right, kSmallest);
    }
}


/**
 * Runtime: 1 ms, faster than 99.47% of Java online submissions for Kth Largest Element in an Array.
 *
 * Memory Usage: 41.4 MB, less than 5.18% of Java online submissions for Kth Largest Element in an Array.
 *
 * Copy from: https://leetcode.cn/problems/kth-largest-element-in-an-array/solutions/307351/shu-zu-zhong-de-di-kge-zui-da-yuan-su-by-leetcode-/[数组中的第K个最大元素-题解^]
 *
 * @author D瓜哥 · https://www.diguage.com
 * @since 2020-01-26 19:39
 */
public int findKthLargest(int[] nums, int k) {
    this.nums = nums;
    int size = nums.length;
    return quickselect(0, size - 1, size - k);
}

/**
 * Runtime: 6 ms, faster than 62.37% of Java online submissions for Kth Largest Element in an Array.
 *
 * Memory Usage: 40.9 MB, less than 5.18% of Java online submissions for Kth Largest Element in an Array.
 */
public int findKthLargestHeap(int[] nums, int k) {
    PriorityQueue<Integer> heap = new PriorityQueue<>(Comparator.comparingInt(a -> a));
    for (int num : nums) {
        heap.add(num);
        if (heap.size() > k) {
            heap.poll();
        }
    }
    return heap.poll();
}

public int findKthLargestSort(int[] nums, int k) {
    Arrays.sort(nums);
    return nums[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
/**
 * 参考 https://leetcode.cn/problems/kth-largest-element-in-an-array/solutions/307351/shu-zu-zhong-de-di-kge-zui-da-yuan-su-by-leetcode-/[数组中的第K个最大元素-题解^] 思路后，自己写出来的。
 *
 * @author D瓜哥 · https://www.diguage.com
 * @since 2024-06-18 17:13
 */
public int findKthLargest(int[] nums, int k) {
  int size = nums.length;
  return quickselect(nums, 0, size - 1, size - k);
}

private int quickselect(int[] nums, int left, int right, int k) {
  if (left == right) {
    return nums[k];
  }
  int num = nums[left];
  int l = left - 1, r = right + 1;
  while (l < r) {
    do {
      l++;
    } while (nums[l] < num);
    do {
      r--;
    } while (num < nums[r]);
    if (l < r) {
      int tmp = nums[l];
      nums[l] = nums[r];
      nums[r] = tmp;
    }
  }
  // TODO: 这里为什么需要使用 r ，而不能是 l ？
  if (k <= r) {
    return quickselect(nums, left, r, k);
  } else {
    return quickselect(nums, r + 1, right, 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
/**
 * @author D瓜哥 · https://www.diguage.com
 * @since 2024-09-20 23:27:08
 */
public int findKthLargest(int[] nums, int k) {
  // 第 k 大，即为第 n - k 小
  return quickselect(nums, nums.length - k, 0, nums.length - 1);
}

private int quickselect(int[] nums, int k, int left, int right) {
  if (left == right) {
    return nums[k];
  }
  int pivot = nums[left], l = left - 1, r = right + 1;
  while (l < r) {
    do {
      l++;
    } while (nums[l] < pivot);
    do {
      r--;
    } while (nums[r] > pivot);
    if (l < r) {
      int tmp = nums[l];
      nums[l] = nums[r];
      nums[r] = tmp;
    }
  }
  if (k <= r) {
    return quickselect(nums, k, left, r);
  } else {
    return quickselect(nums, k, r + 1, right);
  }
}

LeetCode: 215. Kth Largest Element in an Array

友情支持

215. Kth Largest Element in an Array

思路分析

参考资料