[Leetcode] Top-K系列问题总结

yPhantom 2020年02月05日 39次浏览

在本篇文章中,我将尝试总结一下Top-K系列问题。何谓Top-K问题,Top-K问题即类似:

215. Kth Largest Element in an Array | 数组中的第K个最大元素

692. Top K Frequent Words | 前K个高频单词

973. K Closest Points to Origin | 最接近远点的K个点

如上的问题。这些问题综合来看都是在说一个事儿:

按照一定顺序从原数据中取前K个数据

Top-K问题属于面试高频问题,也是比较经典的问题,常常是medium难度,掌握其解答模板,秒杀Top-K不在

话下。

问题分析

  • 在我们确认题目是Top-K问题后,比较重要的一点是找到所谓的一定顺序

在215题中很简单,一定顺序就是整数的大小关系。Java中整数比较可以用:

Integer.compareTo(i1, i2);
Long.compareTo(i1, i2);
...

在692题,其一定顺序是由单词的频次+字母abcd的顺序组合而成的。String比较(按照字母顺序)可以用:

s1.compareTo(s2)

在973题中,它的一定顺序指的是每个点离远点的距离远近。

上述三题中的顺序关系最终都会体现在代码中,因此,对Java而言,在明确了一定顺序后,我们需要掌握常见的比较器写法。


  • 掌握数组转list,list转数组,优先队列PriorityQueue转数组的方式

这一点主要是因为题目中给的输入可能是数组和list,而返回的却是list和数组。合适的转换能避免额外的空间复杂度。

数组转list:

方法1:循环遍历添加
方法2:使用Arrays.asList()
List resultList = Arrays.asList(array);
方法3:使用Collections. addAll()
Collections.addAll(resultList,array);
方法4:使用List.of()
此方法为 Java9新增方法,定义在List接口内,并且为静态方法,故可以由类名直接调用。
List resultList = List.of(array);
注意,以上2、3、4方法不能把基本数据类型转化为列表,因为基本数据类型无法泛型化

list转数组

list.toArray()

PriorityQueue转数组

pq.toArray()

解答模板

一共有三种解法,根据题意,可能有些解法不适用或者需要修改:

  • O(N lg N) 时间复杂度 + O(1) 空间复杂度

这是最简单的方式,先用Arrays.sort()排序然后取后面k个元素即可

public int findKthLargest(int[] nums, int k) {
        final int N = nums.length;
        Arrays.sort(nums);
        return nums[N - k];
}

  • O(N lg K) 时间复杂度 + O(K) 空间复杂度

这里是利用大小堆的策略,PriorityQueue优先队列,默认是Java中的最小堆,根结点是最小值,我们可以改变其排序方式使得根结点是我们按照指定顺序得到“最小值”。

最小堆的offerpoll操作都是logN的时间复杂度,这里堆的大小始终<=K,因此是O(NlgK)

public int findKthLargest(int[] nums, int k) {

    final PriorityQueue<Integer> pq = new PriorityQueue<>();
    for(int val : nums) {
        pq.offer(val);

        if(pq.size() > k) {
            pq.poll();
        }
    }
    return pq.peek();
}

  • 最好O(N) / 最坏O(N^2) 的时间复杂度 + O(1) 空间复杂度

基于平均时间复杂度为O(N)的快速选择。快速选择相比快速排序,在每一轮数据搬移之后,只进入剩下的一边进行下一次迭代,而快排两边都进行。

快速选择的时间复杂度的大致计算是 O(N) + O(N/2) + O(N/4) ..... ,最后只和N有关。

以下附上973题利用快速选择策略的解答。Leetcode显示快速选择这种方式在这题中faster than 99.86% of Java online submissions for K Closest Points to Origin.

class Solution {
    public int[][] kClosest(int[][] points, int K) {
        int l = 0, r = points.length - 1;
        while (l <= r) {
            int pos = quickSelect(points, l, r);
            if (pos == K) {
                break;
            } else if (pos > K) {
                r = pos - 1;
            } else {
                l = pos + 1;
            }
        }
        return Arrays.copyOfRange(points, 0, K);
    }
    
    private int quickSelect(int[][] points, int l, int r) {
        int[] pivot = points[l];
        while (l < r) {
            while (l < r && compare(points[r], pivot) >= 0)
                r--;
            points[l] = points[r];
            while (l < r && compare(points[l], pivot) <= 0) {
                l++;
            }
            points[r] = points[l];
        }
        points[l] = pivot;
        return l;
    }
    
    private int compare(int[] a, int[] b) {
        return (a[0] * a[0] + a[1] * a[1]) - (b[0] * b[0] + b[1] * b[1]);
    }
}

快速选择的缺点在于返回的前K个元素是乱序的,而大小堆可以保证顺序,在要求结果要保证顺序时,不能用快速选择。

参考资料

Solution Explained

Three solutions to this classical K-th problem.

快速选择时间复杂度分析