Top K

Share on:

Top K

Overview

主要的思路是O(nlogn)的PriorityQueue / Sort 和 Average O(n)的Quick Select. 还有一个常见的是关于频率,对于Java需要注意一下Override Comparator的写法。

Problems

Quick Select

 1private int quickSelect(int left, int right){
 2    int index = partition(left, right);
 3    if (index == k - 1){
 4        return nums[index];
 5    }else if (index > k - 1){
 6        return quickSelect(left, index - 1);
 7    }else{
 8        return quickSelect(index + 1, right);
 9    }
10}
11
12private int partition(int left, int right){
13    //if (left > right) return -1; 
14    if (left == right) return left;
15    Random rand = new Random();
16    int pivot_index = left + rand.nextInt(right - left);
17    swap(pivot_index, right);
18    int pivot = nums[right];
19    int i = left;
20    for (int j = left; j < right; j++){
21        if (pivot < nums[j]){
22            swap(j, i);
23            i++;
24        }
25    }
26    swap(i, right);
27    return i;
28}
29
30private void swap(int i, int j){
31    int tmp = nums[i];
32    nums[i] = nums[j];
33    nums[j] = tmp;
34}

如果是从大到小,在pivot和nums[j]比较的时候,我们需要的是找到pivot的正确位置顺便把比pivot大的放到前面,而i是负责最后的位置,所以pivot < nums[j] 交换i, j