[LeetCode][215. Kth Largest Element in an Array] 3 Approaches: Sorting, Priority Queue and Divide and Conquer

发表于 更新于 分类于 Waline： 阅读次数： 本文字数： 2.3k 阅读时长 ≈ 2 分钟

By Long Luo

This article is the solution 3 Approaches: Sorting, Priority Queue and Divide and Conquer of Problem 215. Kth Largest Element in an Array.

Here shows 3 Approaches to slove this problem: Sorting, Priority Queue, Divide and Conquer.

Sorting

Sort the array first, then the \(k-th\) element of the array.

1
2
3
4
5
6
7
8
9
public int findKthLargest(int[] nums, int k) {
    if (nums == null || nums.length == 0) {
        return 0;
    }

    int len = nums.length;
    Arrays.sort(nums);
    return nums[len - k];
}

Analysis

  • Time Complexity: \(O(n \log n)\).
  • Space Complexity: \(O(\log n)\).

Priority Queue

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int findKthLargest_pq(int[] nums, int k) {
    PriorityQueue<Integer> pq = new PriorityQueue<>(k, Comparator.comparingInt(a -> a));

    for (int i = 0; i < k; i++) {
        pq.offer(nums[i]);
    }

    for (int i = k; i < nums.length; i++) {
        if (nums[i] > pq.peek()) {
            pq.poll();
            pq.offer(nums[i]);
        }
    }

    return pq.peek();
}

Analysis

  • Time Complexity: \(O(n \log k)\).
  • Space Complexity: \(O(k)\).

Divide and Conquer

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
class Solution {
    public Random random = new Random(System.currentTimeMillis());

    public int findKthLargest(int[] nums, int k) {
        int len = nums.length;
        int target = len - k;

        int left = 0;
        int right = len - 1;

        while (true) {
            int pivotIndex = partition(nums, left, right);
            if (pivotIndex == target) {
                return nums[pivotIndex];
            } else if (pivotIndex < target) {
                left = pivotIndex + 1;
            } else {
                // pivotIndex > target
                right = pivotIndex - 1;
            }
        }
    }

    public int partition(int[] nums, int left, int right) {
        int randomIndex = left + random.nextInt(right - left + 1);
        swap(nums, left, randomIndex);

        // all in nums[left + 1..le) <= pivot;
        // all in nums(ge..right] >= pivot;
        int pivot = nums[left];
        int le = left + 1;
        int ge = right;

        while (true) {
            while (le <= ge && nums[le] < pivot) {
                le++;
            }

            while (le <= ge && nums[ge] > pivot) {
                ge--;
            }

            if (le >= ge) {
                break;
            }
            swap(nums, le, ge);
            le++;
            ge--;
        }

        swap(nums, left, ge);
        return ge;
    }

    private void swap(int[] nums, int index1, int index2) {
        int temp = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = temp;
    }
}

Analysis

  • Time Complexity: \(O(n)\).
  • Space Complexity: \(O(1)\).

All suggestions are welcome. If you have any query or suggestion please comment below. Please upvote👍 if you like💗 it. Thank you:-)

Explore More Leetcode Solutions. 😉😃💗