TopN问题

// 堆排序
public List<Integer> topKFrequent(int[] nums, int k) {
        //  时间复杂度：O(n)
    Map<Integer, Integer> map = new HashMap<>();
    for (int num : nums) {
        map.put(num, map.getOrDefault(num, 0) + 1);
    }


    // 时间复杂度：O(n) * O(logn)
    PriorityQueue<Integer> queue = new PriorityQueue<>(nums.length, (o1, o2) -> map.get(o1) - map.get(o2));
    for (Integer key : map.keySet()) {
        queue.add(key);
        if (queue.size() > k) {
            queue.poll();
        }
    }


    // 时间复杂度：O(k)
    List<Integer> result = new LinkedList<>();
    while (!queue.isEmpty()) {
        result.add(queue.poll());
    }


    // 时间复杂度：O(k)
    Collections.reverse(result);
    return result;
}


// 桶排序
public List<Integer> topKFrequent(int[] nums, int k) {
    //  时间复杂度：O(n)
    Map<Integer, Integer> map = new HashMap<>();
    for (int num : nums) {
        map.put(num, map.getOrDefault(num, 0) + 1);
    }


    // 时间复杂度：O(n)
    List<Integer>[] buckets = new List[nums.length + 1];
    for (Integer key : map.keySet()) {
        int i = map.get(key);
        if (buckets[i] == null) {
            buckets[i] = new ArrayList<>();
        }
        buckets[i].add(key);
    }


    // 时间复杂度：O(n)
    List<Integer> result = new LinkedList<>();
    for (int i = buckets.length - 1; i > 0; i--) {
        if (buckets[i] == null) {
            continue;
        }
        for (Integer value : buckets[i]) {
            if (result.size() >= k) {
                return result;
            }
            result.add(value);
        }
    }
    return result;
}

// Java 桶排序
public List<String> topKFrequent(String[] words, int k) {


    //  时间复杂度：O(n)
    Map<String, Integer> map = new HashMap<>();
    for (String word : words) {
        map.put(word, map.getOrDefault(word, 0) + 1);
    }


    PriorityQueue<String>[] buckets = new PriorityQueue[words.length + 1];
    for (String key : map.keySet()) {
        int i = map.get(key);
        if (buckets[i] == null) {
            buckets[i] = new PriorityQueue();
        }
        buckets[i].add(key);
    }


    // 时间复杂度：O(n)
    List<String> result = new LinkedList<>();
    for (int i = buckets.length - 1; i > 0; i--) {
        if (buckets[i] == null) {
            continue;
        }
        while (!buckets[i].isEmpty()) {
            if (result.size() >= k) {
                return result;
            }
            result.add(buckets[i].poll());
        }
    }


    return result;
}


// Scala（MapReduce思想，效率不高）
def topKFrequent(words: Array[String], k: Int): List[String] = {
    val result = words.map((_, 1))
                                 .groupBy(_._1)
                                 .map(x => (x._1, x._2.size)).toList
                                 .sortWith((x, y) => x._2 > y._2 || (x._2 == y._2 && x._1 < y._1)).take(k)
                                 .map(_._1)
    result
}