347&692. 前K个高频元素&前K个高频单词
Java刷题
剑指offer
发布日期:   2021-04-05
作者:   欧阳思海
文章字数:   2.1k
阅读时长:   9 分
阅读次数:  
本人花费半年的时间总结的《Java面试指南》已拿腾讯等大厂offer，已开源在github ，欢迎star！

本文GitHub https://github.com/OUYANGSIHAI/JavaInterview 已收录，这是我花了6个月总结的一线大厂Java面试总结，本人已拿大厂offer，欢迎star

原文链接：blog.ouyangsihai.cn >> 347&692. 前K个高频元素&前K个高频单词

堆排序知识介绍请查看文章：

347. 前 K 个高频元素

本题来自 leetCode：347. 前 K 个高频元素[1]

题目详情

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

示例 1:


输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]

示例 2:


输入: nums = [1], k = 1
输出: [1]

说明：

你可以假设给定的 k总是合理的，且 1 ≤ k ≤ 数组中不相同的元素的个数。
你的算法的时间复杂度必须优于 O(n*logn) ,  n是数组的大小。

题目分析

  • 首先统计各整数出现的频率；
  • 维护一个元素数目为`k`的最小堆；
  • 每次都将新的元素与堆顶元素（堆中频率最小的元素）进行比较；
  • 如果新的元素的频率比堆顶端的元素大，则弹出堆顶端的元素，将新的元素添加进堆中；
  • 最后堆中的`k`个元素即为前`k`个高频元素 (不一定是有序的，最后没有再排）

    • 具体实现

    
class Solution {

    public ListInteger topKFrequent(int[] nums, int k) {

        // 统计各数出现的频率
        SetMap.EntryInteger, Integer entrySet = count(nums);

        Map.EntryInteger, Integer[] heap = new Map.Entry[k];
        IteratorMap.EntryInteger, Integer iterator = entrySet.iterator();
        for (int i = 0; i  k; i++) {
            heap[i] = iterator.next();
            iterator.remove();
        }
        // 排序
        heapSort(heap, entrySet, k);
        // 输出
        return output(heap);
    }

    public SetMap.EntryInteger, Integer count(int[] nums) {
        MapInteger, Integer table = new HashMap();

        for (int num : nums) {
            Integer count = table.getOrDefault(num, 0);
            table.put(num, count + 1);
        }

        return table.entrySet();
    }

    public ListInteger output(Map.Entry[] heap) {
        ListInteger topK = new ArrayList();
        for (int i = 0; i  heap.length; i ++) {
            topK.add((Integer)heap[i].getKey());
        }
        return topK;
    }

    /**
     * 大根堆排序后的顺序为从小到大，只需要前k个元素有序
     * @param heap
     * @param entrySet
     */
    public void heapSort(Map.Entry[] heap, SetMap.EntryInteger, Integer entrySet, int k) {
        // 小根堆
        BiPredicateMap.Entry, Map.Entry predicate = (a, b) - (Integer) a.getValue()  (Integer) b.getValue();

        // 先初始化最小堆
        buildHeap(heap, k, predicate);

        // 获取前k个频率高的值
        for(Map.Entry entry : entrySet) {
            // 小根堆堆顶的元素是最小值，若新加入的值大于堆顶堆顶元素，则置换
            if(predicate.test(heap[0], entry)) {
                heap[0] = entry;
                // 由于堆结构发生了变化，需要继续对根元素nums[0]进行调整
                adjustHeap(heap, 0, k, predicate);
            }
        }
    }

    /**
     * 先初始化小根堆，使其满足所有非叶子节点：父节点的值小于子节点的值；
     * @param heap
     * @param length
     */
    public void buildHeap(Map.Entry[] heap, int length, BiPredicateMap.Entry, Map.Entry predicate) {
        //最后一个非叶子节点的位置为`n / 2 - 1`，从后向前，依次堆化
        for(int i = (length  1) - 1; i = 0; i --) {
            adjustHeap(heap, i, length, predicate);
        }
    }

    /**
     * 堆化，使得父节点的值小于子节点的值
     * @param heap 堆数组
     * @param parent 待调整的非叶子节点
     * @param length 调整范围
     */
    public void adjustHeap(Map.Entry[] heap, int parent, int length, BiPredicateMap.Entry, Map.Entry predicate) {

        // index位置节点的左子节点的位置为2 * i + 1
        int left = (parent  1) + 1;
        // index位置节点的右子节点的位置为2 * i + 2
        int right = (parent  1) + 2;

        // 存储父节点、左子节点、右子节点三者最小值的位置
        int temp = parent;

        // 比较父节点和左子节点的大小，
        if(left  length && predicate.test(heap[left], heap[temp])) {
            temp = left;
        }

        // 比较父节点和右子节点的大小
        if(right  length && predicate.test(heap[right], heap[temp])) {
            temp = right;
        }

        // 若父节点的值不是三者最小的
        if(temp != parent) {
            // 则交换和最小值子节点的值
            swap(heap, parent, temp);
            // 并继续调整子节点，使其堆化
            adjustHeap(heap, temp, length, predicate);
        }
    }

    /**
     * 交换数组heap中i和j的值
     * @param heap
     * @param i
     * @param j
     */
    public void swap(Map.Entry[] heap, int i, int j) {
        Map.Entry temp = heap[i];
        heap[i] = heap[j];
        heap[j] = temp;
    }
}

    复杂度分析

    时间复杂度： O(n*log(k))。其中：

  • 方法`count()`的复杂度是`O(n)`；
  • 方法`heapSort()`的复杂度是`O(nlog(k))`；
  • 方法`output()`的复杂度是`O(k)`;

    • 空间复杂度： O(n)，存储哈希表的开销。

    692. 前 K 个高频单词

    本题来自 LeetCode：692. 前 K 个高频单词[2]

    题目详情

    给一非空的单词列表，返回前  k  个出现次数最多的单词。
    返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率，按字母顺序排序。
    示例 1：

    
输入: ["i", "love", "leetcode", "i", "love", "coding"], k = 2
输出: ["i", "love"]
解析: "i" 和 "love" 为出现次数最多的两个单词，均为2次。
注意，按字母顺序 "i" 在 "love" 之前。

    示例 2：

    
输入: ["the", "day", "is", "sunny", "the", "the", "the", "sunny", "is", "is"], k = 4
输出: ["the", "is", "sunny", "day"]
解析: "the", "is", "sunny" 和 "day" 是出现次数最多的四个单词，
    出现次数依次为 4, 3, 2 和 1 次。

    注意：

  • 假定 k 总为有效值， `1≤ k≤集合元素数`。
  • 输入的单词均由小写字母组成。

    • 扩展练习：尝试以   O(nlogk)时间复杂度和 O(n)空间复杂度解决。

    题目分析

  • 该题和`347.前K个高频元素`不同的地方在于输出结果需要按照单词出现频率由高到低排序，并且如果不同的单词有相同出现频率，按字母顺序排序。
  • 改动点 1：对`predicate`的比较条件，增加相同频率时，按字母顺序排序；
  • 改动点 2：获得前`k`个出现频率高的单词后，对这`k`个元素进行堆排列调整；

    • 题目实现

    
class Solution {

    public ListString topKFrequent(String[] words, int k) {

        // 统计各单词出现的频率
        SetMap.EntryString, Integer entrySet = count(words);

        Map.EntryString, Integer[] heap = new Map.Entry[k];
        IteratorMap.EntryString, Integer iterator = entrySet.iterator();
        for (int i = 0; i  k; i++) {
            heap[i] = iterator.next();
            iterator.remove();
        }
        // 排序
        heapSort(heap, entrySet, k);
        // 输出
        return output(heap);
    }

    public SetMap.EntryString, Integer count(String[] nums) {
        MapString, Integer table = new HashMap();

        for (String num : nums) {
            Integer count = table.getOrDefault(num, 0);
            table.put(num, count + 1);
        }

        return table.entrySet();
    }

    public ListString output(Map.Entry[] heap) {
        ListString topK = new ArrayList();
        for (int i = 0; i  heap.length; i ++) {
            topK.add((String)heap[i].getKey());
        }
        return topK;
    }

    /**
     * 大根堆排序后的顺序为从小到大，只需要前k个元素有序
     * @param heap
     * @param entrySet
     */
    public void heapSort(Map.Entry[] heap, SetMap.EntryString, Integer entrySet, int k) {
        // 小根堆，同时根据首字母排序
        BiPredicateMap.Entry, Map.Entry predicate = (a, b) - {
            if(a.getValue().equals(b.getValue())) {
                String ka = (String) a.getKey();
                String kb = (String) b.getKey();
                return ka.compareTo(kb)  0;
            }
            return (Integer) a.getValue()  (Integer) b.getValue();
        };

        // 先初始化最小堆
        buildHeap(heap, k, predicate);

        // 获取前k个频率高的值
        for(Map.Entry entry : entrySet) {
            // 小根堆堆顶的元素是最小值，若新加入的值大于堆顶堆顶元素，则置换
            if(predicate.test(heap[0], entry)) {
                heap[0] = entry;
                // 由于堆结构发生了变化，需要继续对根元素nums[0]进行调整
                adjustHeap(heap, 0, k, predicate);
            }
        }

        // 调整堆，进入排序逻辑
        for (int i = k - 1; i  0 ; i --) {
            swap(heap, 0, i);
            adjustHeap(heap, 0, i, predicate);
        }
    }

    /**
     * 先初始化小根堆，使其满足所有非叶子节点：父节点的值小于子节点的值；
     * @param heap
     * @param length
     */
    public void buildHeap(Map.Entry[] heap, int length, BiPredicateMap.Entry, Map.Entry predicate) {
        //最后一个非叶子节点的位置为`n / 2 - 1`，从后向前，依次堆化
        for(int i = (length  1) - 1; i = 0; i --) {
            adjustHeap(heap, i, length, predicate);
        }
    }

    /**
     * 堆化，使得父节点的值小于子节点的值
     * @param heap 堆数组
     * @param parent 待调整的非叶子节点
     * @param length 调整范围
     */
    public void adjustHeap(Map.Entry[] heap, int parent, int length, BiPredicateMap.Entry, Map.Entry predicate) {

        // index位置节点的左子节点的位置为2 * i + 1
        int left = (parent  1) + 1;
        // index位置节点的右子节点的位置为2 * i + 2
        int right = (parent  1) + 2;

        // 存储父节点、左子节点、右子节点三者最小值的位置
        int temp = parent;

        // 比较父节点和左子节点的大小，
        if(left  length && predicate.test(heap[left], heap[temp])) {
            temp = left;
        }

        // 比较父节点和右子节点的大小
        if(right  length && predicate.test(heap[right], heap[temp])) {
            temp = right;
        }

        // 若父节点的值不是三者最小的
        if(temp != parent) {
            // 则交换和最小值子节点的值
            swap(heap, parent, temp);
            // 并继续调整子节点，使其堆化
            adjustHeap(heap, temp, length, predicate);
        }
    }

    /**
     * 交换数组heap中i和j的值
     * @param heap
     * @param i
     * @param j
     */
    public void swap(Map.Entry[] heap, int i, int j) {
        Map.Entry temp = heap[i];
        heap[i] = heap[j];
        heap[j] = temp;
    }
}

    复杂度分析

    时间复杂度： O(n*log(k))。其中：

  • 方法`count()`的复杂度是`O(n)`；
  • 方法`heapSort()`的复杂度是`O(nlog(k))`；
  • 方法`output()`的复杂度是`O(k)`;

    • 空间复杂度： O(n)，存储哈希表的开销。

    参考资料

    1. 前 K 个高频元素: https://leetcode-cn.com/problems/top-k-frequent-elements/

    2. 前K个高频单词: https://leetcode-cn.com/problems/top-k-frequent-words/

    原文始发于微信公众号（xiaogan的技术博客）：

    本人花费半年的时间总结的《Java面试指南》已拿腾讯等大厂offer，已开源在github ，欢迎star！

    本文GitHub https://github.com/OUYANGSIHAI/JavaInterview 已收录，这是我花了6个月总结的一线大厂Java面试总结，本人已拿大厂offer，欢迎star

    原文链接：blog.ouyangsihai.cn >> 347&692. 前K个高频元素&前K个高频单词

    赏

      转载请注明: 好好学java 347&692. 前K个高频元素&前K个高频单词

     上一篇
    198. 打家劫舍 198. 打家劫舍
    本题来自 LeetCode：198. 打家劫舍[1] 题目详情你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动
    2021-04-05 剑指offer
    Java刷题
    下一篇 
    LeetCode(347) 数组中的第 K 个最大元素（堆排序） LeetCode(347) 数组中的第 K 个最大元素（堆排序）
    一般情况下，题目中有出现前 N个最大（小）值 topN、第 k个最大（小）值，均可以用堆排序来解答，本文来学习下 堆排序的相关知识。 基本概念 堆排序（ Heapsort）是指利用 堆所设计的一种排序算法。 堆是一个近似 完全二叉树的结构，
    2021-04-05 剑指offer
    Java刷题