关注Java领域相关技术 记录有趣的事情

LeetCode-347. 前 K 个高频元素

US-B.Ralph
US-B.Ralph
2020-09-07

问题地址

LeetCode每日一题/2020-09-07

LeetCode347. 前 K 个高频元素

问题描述

规则

  • 给定一个非空的整数数组，返回其中出现频率前 k 高的元素。

示例

  • 示例一：
输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]
  • 示例二：
输入: nums = [1], k = 1
输出: [1]

提示：

  • 你可以假设给定的 k 总是合理的，且 1 ≤ k ≤ 数组中不相同的元素的个数。
  • 你的算法的时间复杂度必须优于 O(n log n) , n 是数组的大小。
  • 题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的。
  • 你可以按任意顺序返回答案。

解析

解题思路

  • 遍历原数组，并使用哈希表建立数字与出现频次的映射关系；
  • 对哈希表进行排序；
  • 遍历排序结果，找出出现频率前k的元素；

数据操作分析

复杂度分析

  1. 时间复杂度，O(nlogn)。首先遍历原数组，并使用哈希表记录出现次数，时间复杂度为 O(n) 。随后，排序算法时间复杂度为O(klogk)。
  2. 空间复杂度，O(n)，最极端的情况下（每个元素都不同），用于存储元素及其频率的 Map 需要存储 n 个键值对。

编码实现

/**
 * LeetCode347
 */
public class LeetCode0347_TopKkFrequentElements {
    public int[] topKFrequent(int[] nums, int k) {

        int[] result = new int[k];

        if (k == 0 || k > result.length) return result;

        Map<Integer, Integer> map = new TreeMap<>();
        for (int i = 0; i < nums.length; i++) {
            Integer count = map.get(nums[i]);
            if (count == null) count = new Integer(0);
            count++;
            map.put(nums[i], count);
        }

        List<Map.Entry<Integer, Integer>> list = new ArrayList<>(map.entrySet());
        Collections.sort(list, new Comparator<Map.Entry<Integer, Integer>>() {
            @Override
            public int compare(Map.Entry<Integer, Integer> o1, Map.Entry<Integer, Integer> o2) {
                return o2.getValue().compareTo(o1.getValue());
            }
        });

        for (int i = 0; i < k; i++) {
            result[i] = list.get(i).getKey();
        }

        return result;
    }
}

官方解法

堆

思路：

  • 首先遍历整个数组，并使用哈希表记录每个数字出现的次数，并形成一个「出现次数数组」。找出原数组的前 k 个高频元素，就相当于找出「出现次数数组」的前 k 大的值。
  • 最简单的做法是给「出现次数数组」排序。但由于可能有 O(N) 个不同的出现次数（其中 N 为原数组长度），故总的算法复杂度会达到 O(N\log N)，不满足题目的要求。
  • 在这里，我们可以利用堆的思想：建立一个小顶堆，然后遍历「出现次数数组」：
    • 如果堆的元素个数小于 k，就可以直接插入堆中。
    • 如果堆的元素个数等于 k，则检查堆顶与当前出现次数的大小。如果堆顶更大，说明至少有 k 个数字的出现次数比当前值大，故舍弃当前值；否则，就弹出堆顶，并将当前值插入堆中。
  • 遍历完成后，堆中的元素就代表了「出现次数数组」中前 k 大的值。

复杂度分析：

  1. 时间复杂度，O(Nlogk)，其中 N 为数组的长度。我们首先遍历原数组，并使用哈希表记录出现次数，每个元素需要 O(1) 的时间，共需 O(N) 的时间。随后，我们遍历「出现次数数组」，由于堆的大小至多为 k，因此每次堆操作需要 O(\log k) 的时间，共需 O(N\log k) 的时间。二者之和为 O(N\log k)。
  2. 空间复杂度，O(N)。哈希表的大小为 O(N)，而堆的大小为 O(k)，共计为 O(N)。

编码实现

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> occurrences = new HashMap<Integer, Integer>();
        for (int num : nums) {
            occurrences.put(num, occurrences.getOrDefault(num, 0) + 1);
        }

        // int[] 的第一个元素代表数组的值，第二个元素代表了该值出现的次数
        PriorityQueue<int[]> queue = new PriorityQueue<int[]>(new Comparator<int[]>() {
            public int compare(int[] m, int[] n) {
                return m[1] - n[1];
            }
        });
        for (Map.Entry<Integer, Integer> entry : occurrences.entrySet()) {
            int num = entry.getKey(), count = entry.getValue();
            if (queue.size() == k) {
                if (queue.peek()[1] < count) {
                    queue.poll();
                    queue.offer(new int[]{num, count});
                }
            } else {
                queue.offer(new int[]{num, count});
            }
        }
        int[] ret = new int[k];
        for (int i = 0; i < k; ++i) {
            ret[i] = queue.poll()[0];
        }
        return ret;
    }
}

基于快速排序

思路：

  • 我们可以使用基于快速排序的方法，求出「出现次数数组」的前 k 大的值。
  • 在对数组 \textit{arr}[l \ldots r] 做快速排序的过程中，我们首先将数组划分为两个部分 \textit{arr}[i \ldots q-1] 与 \textit{arr}[q+1 \ldots j]，并使得 \textit{arr}[i \ldots q-1] 中的每一个值都不超过 \textit{arr}[q]，且 \textit{arr}[q+1 \ldots j] 中的每一个值都大于 \textit{arr}[q]。
  • 于是，我们根据 k 与左侧子数组 \textit{arr}[i \ldots q-1] 的长度（为 q−i）的大小关系：
    • 如果 k \le q-i，则数组 \textit{arr}[l \ldots r] 前 k 大的值，就等于子数组 \textit{arr}[i \ldots q-1] 前 k 大的值。
    • 否则，数组 \textit{arr}[l \ldots r] 前 k 大的值，就等于左侧子数组全部元素，加上右侧子数组 \textit{arr}[q+1 \ldots j] 中前 k – (q – i)大的值。
  • 原版的快速排序算法的平均时间复杂度为 O(N\log N)。我们的算法中，每次只需在其中的一个分支递归即可，因此算法的平均时间复杂度降为 O(N)。

复杂度分析：

  1. 时间复杂度，O(N^2)，其中 N 为数组的长度。
    • 设处理长度为 N 的数组的时间复杂度为 f(N)。由于处理的过程包括一次遍历和一次子分支的递归，最好情况下，有 f(N) = O(N) + f(N/2)，根据 主定理，能够得到 f(N) = O(N)。
    • 最坏情况下，每次取的中枢数组的元素都位于数组的两端，时间复杂度退化为 O(N^2)。但由于我们在每次递归的开始会先随机选取中枢元素，故出现最坏情况的概率很低。
    • 平均情况下，时间复杂度为 O(N)。
  2. 空间复杂度，O(N)。哈希表的大小为 O(N)，用于排序的数组的大小也为 O(N)，快速排序的空间复杂度最好情况为 O(\log N)，最坏情况为 O(N)。

编码实现

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> occurrences = new HashMap<Integer, Integer>();
        for (int num : nums) {
            occurrences.put(num, occurrences.getOrDefault(num, 0) + 1);
        }

        List<int[]> values = new ArrayList<int[]>();
        for (Map.Entry<Integer, Integer> entry : occurrences.entrySet()) {
            int num = entry.getKey(), count = entry.getValue();
            values.add(new int[]{num, count});
        }
        int[] ret = new int[k];
        qsort(values, 0, values.size() - 1, ret, 0, k);
        return ret;
    }

    public void qsort(List<int[]> values, int start, int end, int[] ret, int retIndex, int k) {
        int picked = (int) (Math.random() * (end - start + 1)) + start;
        Collections.swap(values, picked, start);

        int pivot = values.get(start)[1];
        int index = start;
        for (int i = start + 1; i <= end; i++) {
            if (values.get(i)[1] >= pivot) {
                Collections.swap(values, index + 1, i);
                index++;
            }
        }
        Collections.swap(values, start, index);

        if (k <= index - start) {
            qsort(values, start, index - 1, ret, retIndex, k);
        } else {
            for (int i = start; i <= index; i++) {
                ret[retIndex++] = values.get(i)[0];
            }
            if (k > index - start + 1) {
                qsort(values, index + 1, end, ret, retIndex, k - (index - start + 1));
            }
        }
    }
}

引申

本题与 215. 数组中的第K个最大元素 具有诸多相似之处。

精彩评论

跳转地址：347. 前 K 个高频元素

解法一：粗暴排序法

思路

  • 最简单粗暴的思路就是 使用排序算法对元素按照频率由高到低进行排序，然后再取前 k 个元素。

  • 以下十种排序算法，任你挑选！

  • 可以发现，使用常规的诸如 冒泡、选择、甚至快速排序都是不满足题目要求，它们的时间复杂度都是大于或者等于 O(nlog⁡n)，而题目要求算法的时间复杂度必须优于 O(nlogn)。

复杂度分析

  1. 时间复杂度：O(nlogn)，n 表示数组长度。首先，遍历一遍数组统计元素的频率，这一系列操作的时间复杂度是 O(n)；接着，排序算法时间复杂度为 O(nlogn)；因此整体时间复杂度为 O(nlogn)。
  2. 空间复杂度：O(n)，最极端的情况下（每个元素都不同），用于存储元素及其频率的 Map 需要存储 n 个键值对。

解法二：最小堆

思路

  • 题目最终需要返回的是前 k 个频率最大的元素，可以想到借助堆这种数据结构，对于 k 频率之后的元素不用再去处理，进一步优化时间复杂度。
  • 具体操作为：
    • 借助 哈希表 来建立数字和其出现次数的映射，遍历一遍数组统计元素的频率
    • 维护一个元素数目为 k 的最小堆
    • 每次都将新的元素与堆顶元素（堆中频率最小的元素）进行比较
    • 如果新的元素的频率比堆顶端的元素大，则弹出堆顶端的元素，将新的元素添加进堆中
      最终，堆中的 k 个元素即为前 k 个高频元素

复杂度分析

  1. 时间复杂度：O(nlogn)，n 表示数组的长度。首先，遍历一遍数组统计元素的频率，这一系列操作的时间复杂度是 O(n)；接着，遍历用于存储元素频率的 map，如果元素的频率大于最小堆中顶部的元素，则将顶部的元素删除并将该元素加入堆中，这里维护堆的数目是 k，所以这一系列操作的时间复杂度是 O(nlogk) 的；因此，总的时间复杂度是 O(nlog⁡k)。
  2. 空间复杂度：O(n)，最坏情况下（每个元素都不同），map 需要存储 n 个键值对，优先队列需要存储 k 个元素，因此，空间复杂度是 O(n)。

编码实现

class Solution {
    public List<Integer> topKFrequent(int[] nums, int k) {
        // 使用字典，统计每个元素出现的次数，元素为键，元素出现的次数为值
        HashMap<Integer,Integer> map = new HashMap();
        for(int num : nums){
            if (map.containsKey(num)) {
               map.put(num, map.get(num) + 1);
             } else {
                map.put(num, 1);
             }
        }
        // 遍历map，用最小堆保存频率最大的k个元素
        PriorityQueue<Integer> pq = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer a, Integer b) {
                return map.get(a) - map.get(b);
            }
        });
        for (Integer key : map.keySet()) {
            if (pq.size() < k) {
                pq.add(key);
            } else if (map.get(key) > map.get(pq.peek())) {
                pq.remove();
                pq.add(key);
            }
        }
        // 取出最小堆中的元素
        List<Integer> res = new ArrayList<>();
        while (!pq.isEmpty()) {
            res.add(pq.remove());
        }
        return res;
    }
}
US-B.Ralph
LeetCode数据结构与算法算法

Leave a Comment

邮箱地址不会被公开。 必填项已用*标注

1 × 2 =