LeetCode题解215.kth-largest-element-in-an-array

题目地址

https://leetcode.com/problems/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
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.

思路

这道题要求在一个无序的数组中，返回第K大的数。根据时间复杂度不同，这题有3种不同的解法。

解法一 （排序）

很直观的解法就是给数组排序，这样求解第K大的数，就等于是从小到大排好序的数组的第(n-K)小的数 (n 是数组的长度）。

例如：

[3,2,1,5,6,4], k = 2
1. 数组排序：
 [1,2,3,4,5,6]，
2. 找第（n-k）小的数
 n-k=4, nums[4]=5 (第2大的数）

时间复杂度: O(nlogn) - n 是数组长度。

解法二 - 小顶堆（Heap）

可以维护一个大小为K的小顶堆，堆顶是最小元素，当堆的size > K 的时候，删除堆顶元素.
扫描一遍数组，最后堆顶就是第K大的元素。 直接返回。

例如：

时间复杂度：O(n * logk) , n is array length
空间复杂度：O(k)

跟排序相比，以空间换时间。

解法三 - Quick Select

Quick Select 类似快排，选取pivot，把小于pivot的元素都移到pivot之前，这样pivot所在位置就是第pivot index 小的元素。
但是不需要完全给数组排序，只要找到当前pivot的位置是否是在第(n-k)小的位置，如果是，找到第k大的数直接返回。

具体步骤：

1. 在数组区间随机取`pivot index = left + random[right-left]`. 
2. 根据pivot 做 partition，在数组区间，把小于pivot的数都移到pivot左边。
3. 得到pivot的位置 index，`compare(index, (n-k))`.
    a. index == n-k -> 找到第`k`大元素，直接返回结果。
    b. index < n-k -> 说明在`index`右边，继续找数组区间`[index+1, right]`
    c. index > n-k -> 那么第`k`大数在`index`左边，继续查找数组区间`[left, index-1]`.

例子，【3,2,3,1,2,4,5,5,6]， k = 4

如下图：

时间复杂度：

• 平均是：O(n)
• 最坏的情况是：O(n * n)

关键点分析

1. 直接排序很简单
2. 堆（Heap）主要是要维护一个K大小的小顶堆，扫描一遍数组，最后堆顶元素即是所求。
3. Quick Select, 关键是是取pivot，对数组区间做partition，比较pivot的位置，类似二分，取pivot左边或右边继续递归查找。

代码（Java code）

解法一 - 排序

class KthLargestElementSort {
 public int findKthlargest2(int[] nums, int k) {
    Arrays.sort(nums);
    return nums[nums.length - k];
  }
}

解法二 - Heap （PriorityQueue）

class KthLargestElementHeap {
  public int findKthLargest(int[] nums, int k) {
      PriorityQueue<Integer> pq = new PriorityQueue<>();
      for (int num : nums) {
        pq.offer(num);
        if (pq.size() > k) {
          pq.poll();
        }
      }
      return pq.poll();
  }
}

解法三 - Quick Select

class KthLargestElementQuickSelect {
    static Random random = new Random();
    public int findKthLargest3(int[] nums, int k) {
      int len = nums.length;
      return select(nums, 0, len - 1, len - k);
    }
    
    private int select(int[] nums, int left, int right, int k) {
      if (left == right) return nums[left];
      // random select pivotIndex between left and right
      int pivotIndex = left + random.nextInt(right - left);
      // do partition, move smaller than pivot number into pivot left
      int pos = partition(nums, left, right, pivotIndex);
      if (pos == k) {
        return nums[pos];
      } else if (pos > k) {
        return select(nums, left, pos - 1, k);
      } else {
        return select(nums, pos + 1, right, k);
      }
    }
    
    private int partition(int[] nums, int left, int right, int pivotIndex) {
      int pivot = nums[pivotIndex];
      // move pivot to end
      swap(nums, right, pivotIndex);
      int pos = left;
      // move smaller num to pivot left
      for (int i = left; i <= right; i++) {
        if (nums[i] < pivot) {
          swap(nums, pos++, i);
        }
      }
      // move pivot to original place
      swap(nums, right, pos);
      return pos;
    }
    
    private void swap(int[] nums, int i, int j) {
      int tmp = nums[i];
      nums[i] = nums[j];
      nums[j] = tmp;
    }
}

参考（References）

1. Quick Select Wiki

bulit-in gradle插件的版本号是多少？ - java

在我的gradle构建文件中，我有以下插件块plugins { `java-library` jacoco checkstyle } 这些都没有指定版本，但是一切正常。假定一个项目正在使用gradle 6.0和gradle包装器，但是系统已安装gradle 5.0。问题：如果我运行gradle wrapper ./gradlew build，将会执行grad…

LeetCode题解169.majority-element

题目地址 https://leetcode.com/problems/majority-element/description/ 题目描述 Given an array of size n, find the majority element. The majority element is the element that appears more tha…

LeetCode题解1104.path-in-zigzag-labelled-binary-tree

题目地址 https://leetcode-cn.com/problems/path-in-zigzag-labelled-binary-tree/description/ 题目描述 在一棵无限的二叉树上，每个节点都有两个子节点，树中的节点 逐行 依次按 “之” 字形进行标记。 如下图所示，在奇数行（即，第一行、第三行、第五行……）中，按从左到右的顺序进行标…

LeetCode题解1019.next-greater-node-in-linked-list

题目地址 https://leetcode-cn.com/problems/next-greater-node-in-linked-list/submissions/ 题目描述 给出一个以头节点 head 作为第一个节点的链表。链表中的节点分别编号为：node_1, node_2, node_3, ... 。 每个节点都可能有下一个更大值（next larg…

LeetCode题解167.two-sum-ii-input-array-is-sorted

题目地址 https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/description/ 题目描述 这是leetcode头号题目two sum的第二个版本，难度简单。 Given an array of integers that is already sorted in ascendi…