【算法题解】 Day16 排序

简介: 今天的算法是 「排序」 相关,“算法题解系列文章旨在精选重点与易错的算法题,总结常见的算法思路与可能出现的错误,以实战习题的形式理解算法,使用算法。”

1046. 最后一块石头的重量

题目

1046. 最后一块石头的重量 难度:easy

有一堆石头,每块石头的重量都是正整数。

每一回合,从中选出两块 最重的 石头,然后将它们一起粉碎。假设石头的重量分别为 x 和 y,且 x <= y。那么粉碎的可能结果如下:

  • 如果 x == y,那么两块石头都会被完全粉碎;
  • 如果 x != y,那么重量为 x 的石头将会完全粉碎,而重量为 y 的石头新重量为 y-x

最后,最多只会剩下一块石头。返回此石头的重量。如果没有石头剩下,就返回 0

示例:

输入:[2,7,4,1,8,1]
输出:1
解释:
先选出 78,得到 1,所以数组转换为 [2,4,1,1,1],
再选出 24,得到 2,所以数组转换为 [2,1,1,1],
接着是 21,得到 1,所以数组转换为 [1,1,1],
最后选出 11,得到 0,最终数组转换为 [1],这就是最后剩下那块石头的重量。
AI 代码解读

提示:

  • 1 <= stones.length <= 30
  • 1 <= stones[i] <= 1000

 

方法一:最大堆

思路

将所有石头的重量放入最大堆中。每次依次从队列中取出最重的两块石头 a 和 b,必有 a≥b。如果 a>b,则将新石头 a-b 放回到最大堆中;如果 a=b,两块石头完全被粉碎,因此不会产生新的石头。重复上述操作,直到剩下的石头少于 2 块。

最终可能剩下 1 块石头,该石头的重量即为最大堆中剩下的元素,返回该元素;也可能没有石头剩下,此时最大堆为空,返回 0。
 

解题

Python:

class Solution:
    def lastStoneWeight(self, stones: List[int]) -> int:
        # 初始化
        heap = [-stone for stone in stones]
        heapq.heapify(heap)

        # 模拟
        while len(heap) > 1:
            x,y = heapq.heappop(heap),heapq.heappop(heap)
            if x != y:
                heapq.heappush(heap,x-y)

        if heap: return -heap[0]
        return 0
AI 代码解读

Java:

class Solution {
    public int lastStoneWeight(int[] stones) {
        PriorityQueue<Integer> pq = new PriorityQueue<Integer>((a, b) -> b - a);
        for (int stone : stones) {
            pq.offer(stone);
        }

        while (pq.size() > 1) {
            int a = pq.poll();
            int b = pq.poll();
            if (a > b) {
                pq.offer(a - b);
            }
        }
        return pq.isEmpty() ? 0 : pq.poll();
    }
}
AI 代码解读

 

692. 前K个高频单词

题目

692. 前K个高频单词 难度:medium

给定一个单词列表 words 和一个整数 k ,返回前 k 个出现次数最多的单词。

返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率, 按字典顺序 排序。

示例 1:

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

示例 2:

输入: ["the", "day", "is", "sunny", "the", "the", "the", "sunny", "is", "is"], k = 4
输出: ["the", "is", "sunny", "day"]
解析: "the", "is", "sunny""day" 是出现次数最多的四个单词,
    出现次数依次为 4, 3, 21 次。
AI 代码解读

注意:

  • 1 <= words.length <= 500
  • 1 <= words[i] <= 10
  • words[i] 由小写英文字母组成。
  • k 的取值范围是 [1, 不同 words[i] 的数量]

 

方法一:哈希表

思路

我们可以预处理出每一个单词出现的频率,然后依据每个单词出现的频率降序排序,最后返回前 k 个字符串即可。

具体地,我们利用哈希表记录每一个字符串出现的频率,然后将哈希表中所有字符串进行排序,排序时,如果两个字符串出现频率相同,那么我们让两字符串中字典序较小的排在前面,否则我们让出现频率较高的排在前面。最后我们只需要保留序列中的前 k 个字符串即可。
 

解题

Java:

class Solution {
    public List<String> topKFrequent(String[] words, int k) {
        Map<String, Integer> cnt = new HashMap<String, Integer>();
        for (String word : words) {
            cnt.put(word, cnt.getOrDefault(word, 0) + 1);
        }
        List<String> rec = new ArrayList<String>();
        for (Map.Entry<String, Integer> entry : cnt.entrySet()) {
            rec.add(entry.getKey());
        }
        Collections.sort(rec, new Comparator<String>() {
            public int compare(String word1, String word2) {
                return cnt.get(word1) == cnt.get(word2) ? word1.compareTo(word2) : cnt.get(word2) - cnt.get(word1);
            }
        });
        return rec.subList(0, k);
    }
}
AI 代码解读

 

方法二:优先队列

思路

对于前 k 大或前 k 小这类问题,有一个通用的解法:优先队列。优先队列可以在 O(logn) 的时间内完成插入或删除元素的操作(其中 n 为优先队列的大小),并可以 O(1) 地查询优先队列顶端元素。

在本题中,我们可以创建一个小根优先队列(顾名思义,就是优先队列顶端元素是最小元素的优先队列)。我们将每一个字符串插入到优先队列中,如果优先队列的大小超过了 k,那么我们就将优先队列顶端元素弹出。这样最终优先队列中剩下的 k 个元素就是前 k 个出现次数最多的单词。
 

解题

Java:

class Solution {
    public List<String> topKFrequent(String[] words, int k) {
        Map<String, Integer> cnt = new HashMap<String, Integer>();
        for (String word : words) {
            cnt.put(word, cnt.getOrDefault(word, 0) + 1);
        }
        PriorityQueue<Map.Entry<String, Integer>> pq = new PriorityQueue<Map.Entry<String, Integer>>(new Comparator<Map.Entry<String, Integer>>() {
            public int compare(Map.Entry<String, Integer> entry1, Map.Entry<String, Integer> entry2) {
                return entry1.getValue() == entry2.getValue() ? entry2.getKey().compareTo(entry1.getKey()) : entry1.getValue() - entry2.getValue();
            }
        });
        for (Map.Entry<String, Integer> entry : cnt.entrySet()) {
            pq.offer(entry);
            if (pq.size() > k) {
                pq.poll();
            }
        }
        List<String> ret = new ArrayList<String>();
        while (!pq.isEmpty()) {
            ret.add(pq.poll().getKey());
        }
        Collections.reverse(ret);
        return ret;
    }
}
AI 代码解读

 

后记

📝 上篇精讲: 【算法题解】 Day15 栈
💖 我是  𝓼𝓲𝓭𝓲𝓸𝓽,期待你的关注;
👍 创作不易,请多多支持;
🔥 系列专栏: 算法题解
目录
打赏
0
0
0
0
0
分享
相关文章
|
9月前
|
【洛谷 P1223】排队接水(贪心算法+结构体排序)
该问题要求安排n个人的排队顺序以最小化平均等待时间。每个人接水需时Ti,解决方案是让接水时间短的人优先。给定n1000ti106,代码示例使用C++实现,通过排序使时间从小到大排列,然后计算平均等待时间。样例输入为10个人的时间数组,输出为优化后的排队顺序及平均等待时间(291.90)。
76 0
JavaScript 中通过Array.sort() 实现多字段排序、排序稳定性、随机排序洗牌算法、优化排序性能,JS中排序算法的使用详解(附实际应用代码)
Array.sort() 是一个功能强大的方法,通过自定义的比较函数,可以处理各种复杂的排序逻辑。无论是简单的数字排序,还是多字段、嵌套对象、分组排序等高级应用,Array.sort() 都能胜任。同时,通过性能优化技巧(如映射排序)和结合其他数组方法(如 reduce),Array.sort() 可以用来实现高效的数据处理逻辑。 只有锻炼思维才能可持续地解决问题,只有思维才是真正值得学习和分享的核心要素。如果这篇博客能给您带来一点帮助,麻烦您点个赞支持一下,还可以收藏起来以备不时之需,有疑问和错误欢迎在评论区指出~
JS数组操作方法全景图,全网最全构建完整知识网络!js数组操作方法全集(实现筛选转换、随机排序洗牌算法、复杂数据处理统计等情景详解,附大量源码和易错点解析)
这些方法提供了对数组的全面操作,包括搜索、遍历、转换和聚合等。通过分为原地操作方法、非原地操作方法和其他方法便于您理解和记忆,并熟悉他们各自的使用方法与使用范围。详细的案例与进阶使用,方便您理解数组操作的底层原理。链式调用的几个案例,让您玩转数组操作。 只有锻炼思维才能可持续地解决问题,只有思维才是真正值得学习和分享的核心要素。如果这篇博客能给您带来一点帮助,麻烦您点个赞支持一下,还可以收藏起来以备不时之需,有疑问和错误欢迎在评论区指出~
|
7月前
|
【算法】二分查找——在排序数组中查找元素的第一个和最后一个位置
【算法】二分查找——在排序数组中查找元素的第一个和最后一个位置
【排序算法】八大排序(下)(c语言实现)(附源码)
本文继续学习并实现了八大排序算法中的后四种:堆排序、快速排序、归并排序和计数排序。详细介绍了每种排序算法的原理、步骤和代码实现,并通过测试数据展示了它们的性能表现。堆排序利用堆的特性进行排序,快速排序通过递归和多种划分方法实现高效排序,归并排序通过分治法将问题分解后再合并,计数排序则通过统计每个元素的出现次数实现非比较排序。最后,文章还对比了这些排序算法在处理一百万个整形数据时的运行时间,帮助读者了解不同算法的优劣。
218 7
【排序算法】八大排序(上)(c语言实现)(附源码)
本文介绍了四种常见的排序算法:冒泡排序、选择排序、插入排序和希尔排序。通过具体的代码实现和测试数据,详细解释了每种算法的工作原理和性能特点。冒泡排序通过不断交换相邻元素来排序,选择排序通过选择最小元素进行交换,插入排序通过逐步插入元素到已排序部分,而希尔排序则是插入排序的改进版,通过预排序使数据更接近有序,从而提高效率。文章最后总结了这四种算法的空间和时间复杂度,以及它们的稳定性。
169 8
|
5月前
|
解析排序算法:十大排序方法的工作原理与性能比较
解析排序算法:十大排序方法的工作原理与性能比较
153 9
数据结构与算法学习十三:基数排序,以空间换时间的稳定式排序,速度很快。
基数排序是一种稳定的排序算法,通过将数字按位数切割并分配到不同的桶中,以空间换时间的方式实现快速排序,但占用内存较大,不适合含有负数的数组。
69 0
数据结构与算法学习十三:基数排序,以空间换时间的稳定式排序,速度很快。
|
5月前
|
❤️算法笔记❤️-(每日一刷-83、删除排序链表中的重复项)
❤️算法笔记❤️-(每日一刷-83、删除排序链表中的重复项)
54 0
现有一个接口DataOperation定义了排序方法sort(int[])和查找方法search(int[],int),已知类QuickSort的quickSort(int[])方法实现了快速排序算法
该博客文章通过UML类图和Java源码示例,展示了如何使用适配器模式将QuickSort类和BinarySearch类的排序和查找功能适配到DataOperation接口中,实现算法的解耦和复用。
76 1
现有一个接口DataOperation定义了排序方法sort(int[])和查找方法search(int[],int),已知类QuickSort的quickSort(int[])方法实现了快速排序算法

热门文章

最新文章

AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等