该算法查找数组中前 k 个频繁元素的时间和空间复杂度是多少？

Question

这是我必须找到输入数组中前 k 个频繁元素的算法。我使用了带有 Bucketlist 类型数组的 HashMap。我无法理解 Big-O 表示法中的时间和空间复杂度。

谢谢！

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        //HashMap that maps number -> its frequency
        Map<Integer, Integer> freq = new HashMap();
        for(int num : nums) freq.put(num, freq.getOrDefault(num, 0) + 1);

        //Array that contains a list of numbers with frequency equal to that index of the array
        List<Integer>[] bucketList = new ArrayList[nums.length + 1];
        for(int i = 0; i <= nums.length; i++) bucketList[i] = new ArrayList<Integer>();

        for(HashMap.Entry<Integer, Integer> e : freq.entrySet()) {
            bucketList[e.getValue()].add(e.getKey()); 
        }

        //Array with the top k frequencies.
        int[] topK = new int[k];
        for(int i = nums.length; i >=0; i--) {
            if(bucketList[i].size() > 0) {
                for(int n : bucketList[i]) {
                    topK[k-1] = n;
                    k--;
                    if(k == 0) return topK;
                }
            }
        }

        return topK;
    }
}

Answer 1

除了填充频率图的前两行之外，其余的都是简单的计数排序，我建议您阅读更多相关内容。

话虽如此，我已经分解了每一行，并在其旁边写下了复杂性，我用

O(?)

注意到了一个技巧。

n

是

nums

的大小（即

nums.length

）。

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> freq = new HashMap(); // O(1)
        for(int num : nums) { // O(n)
          freq.put(num, freq.getOrDefault(num, 0) + 1); // O(1) because put and getOrDefault are both O(1)
        }
        
        // This is where the counting sort starts
        List<Integer>[] bucketList = new ArrayList[nums.length + 1]; // O(1)
        for(int i = 0; i <= nums.length; i++) bucketList[i] = new ArrayList<Integer>(); // O(n)

        for(HashMap.Entry<Integer, Integer> e : freq.entrySet()) { // O(n)
            bucketList[e.getValue()].add(e.getKey()); //O(1)
        }

        int[] topK = new int[k]; // O(1)
        for(int i = nums.length; i >=0; i--) { // O(n)
            if(bucketList[i].size() > 0) { // O(1)
                for(int n : bucketList[i]) { // O(?) this one is tricky and I will explain it below
                    topK[k-1] = n; // O(1)
                    k--; O(1)
                    if(k == 0) return topK; // O(1)
                }
            }
        }

        return topK; // O(1)
    }
}

时间复杂度为

O(1 + n*1 + 1 + n + n*1 + 1 + n*1*?*1*1*1) = )= O(n+n*?)

。

什么是

O(?)

？一种天真的方法是注意到在最坏的情况下，所有元素都具有相同的频率，因此

bucketList[i]

以

O(n)

为界，这将给出

O(n^2)

。但这个界限还不够紧密。可以通过注意 Sum(bucketList[i]) 以 n 为界来计算一个更严格的界限（更准确地说，它以

d

和

d

为不同数字的数量为界，但

d

以

n

为界） 。 所以这将其减少为

O(n)