《啊哈！算法》读书笔记（第九章）——寻找多数元素问题

ゞ浴缸里的玫瑰 2022-07-16 13:15 133阅读 0赞

**第九章 还能更好吗？——寻找多数元素问题**

**问题：**假如现在有一个序列，已知其中一个数的此书超过50%，请找出这个数。比如3、3、1、1、3、2、3中，出现次数超过50%的数是3。

**答:**

**方法1****：**两两比较，分别记录数字的出现次数，2个for循环就可以解决。时间复杂度O(N^2)。

**方法2****：**排序后再重头到尾扫一遍，用一个count来统计每个数出现的次数，并再用一个变量max来更新count的最大值。排序可以用堆排序或者快排，时间复杂度O(NlogN)。

**方法3****：**排序结束后可以不扫，如果这个数出现的次数大于50%的话，排序之后就应该就是位于n/2位置的那个数。

**方法4****：**用一个数组来记录每个数出现的次数，就是类似桶排序的方法，数组中最大值的下标就是出现次数超过50%的数。时间复杂度和空间复杂度都是O(M+N)。如果数的大小分布跨度很大，比如1,10000,1000000，这样会浪费空间，可以采用离散化解决，比如1对应1,2对应10000,3对应1000000。

**方法5****：**选择一个数作为划分起点，然后用类似快速排序的方法将小于它的移到左边，大于它的移到右边，这样就将所有的数划分为两部分，此时，划分点所在位置为k。如果k>n/2，那么继续用同样的方法在左边部分查找；如果k<n/2就在右边不认查找；k=n/2那么就是这个数。这样比之前的快速排序的方法要快一些，估计近似于O(N)。

**方法6****：**“寻找多元素问题”，我们很容易的看出来，在一个序列中如果去掉2个不同的元素，那么原序列中的出现次数超过50%的数，在新的序列中还是超过50%，因此我们只要按照序列依次扫描，先把A\[0\]赋值给c，增加个计数器，count = 1；然后向右扫描，如果跟c相同，则count++，不同，那么count --，这个真是我们从上面那个结论里得出的，一旦count == 0了，把c赋值为A\[i+1\],count = 1；，重复该过程，直到结束，这个时候，c就是那个超过50%的数。遍历一遍，时间复杂度为O(N)。

**学习算法需要多思考！！！学习算法不能一直学学学，要经常停下来总结与回顾，比较算法的应用场景以及可以解决的问题，比较同一问题采用不同算法的性能。**

**题目是做不完的，算法是复杂多变的。我需要多练习思考问题的方式，而不是一味的多学新知识。**

**![20161118202253417][]**

——配图来源于《啊哈！算法》第九章

[20161118202253417]: /images/20220715/7d4ce72222e1407f87ab3cf726d8ec89.png

发表评论取消回复

表情：

评论列表（有 0 条评论，133人围观）

还没有评论，来说两句吧...

相关阅读

相关每日一练Day05：寻找多数元素

目录多数元素I 1、方法一 2、方法二 -------------------- 这道题来自LeetCode，下面我们来抽丝剥茧，细

落日映苍穹つ/ 2024年04月01日 17:01/ 0 赞/ 88 阅读

相关啊哈算法总结之第一章——排序

在第一章中：对于排序讲了三种：桶排序，冒泡排序，快速排序。桶排序的核心算法: int a[101] = {0}; //将所有数组元素都初始化为0

た入场券/ 2022年09月29日 05:29/ 0 赞/ 173 阅读

相关 Leetcode 169. 多数元素(哈希YYDS)

题目重述给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。你可以假设数组是非空的，并且给定的数组总是存在多

旧城等待，/ 2022年08月30日 15:42/ 0 赞/ 150 阅读

相关《啊哈！算法》读书笔记（第九章）——寻找多数元素问题

第九章还能更好吗？——寻找多数元素问题问题：假如现在有一个序列，已知其中一个数的此书超过50%，请找出这个数。比如3、3、1、1、3、2、3中，出现次数超过50%的数是3

ゞ浴缸里的玫瑰/ 2022年07月16日 13:15/ 0 赞/ 134 阅读

相关《啊哈！算法》读书笔记

《啊哈！算法》零零散散花了一周的时间阅读了《啊哈！算法》。这本书内容相对基础，适合初学者时阅读（当然，大神也可以温故而知新）。《啊哈！算法》这本书中的算法举例贴近生活，语

小灰灰/ 2022年07月16日 13:14/ 0 赞/ 174 阅读

相关 169. Majority Element （寻找多数元素）

Given an array of size n, find the majority element. The majority element is the element

你的名字/ 2022年07月15日 01:20/ 0 赞/ 174 阅读

相关读书笔记：《C++ PrimerPlus》第九章～第十一章

[第一章预备知识][Link 1] [第二章开始学习C++][_C] [第三章处理数据][Link 2] [第四章复合类型][Link 3]

r囧r小猫/ 2022年05月13日 09:04/ 0 赞/ 599 阅读

相关读书笔记-第九章进程关系第十章信号

第十章信号 1..信号是异步事件的经典实例. 2..信号的产生 a..进程自身-->abort b..其他进程 c..内核 2..内核对信号的处理 a

朱雀/ 2022年04月10日 13:40/ 0 赞/ 232 阅读

相关【算法图解】读书笔记：第3章递归

递归 -------------------- 在我看来，递归就类似俄罗斯套娃，一次次重复去执行相同的操作，最后得出结果的过程。很多递归的操作都可以使用循环来替代。

小鱼儿/ 2022年01月20日 00:23/ 0 赞/ 206 阅读

相关 Java核心技术卷一第九章读书笔记

文章目录 9.1 Java集合框架 9.2 具体的集合 9.3 映射

亦凉/ 2021年11月18日 01:06/ 0 赞/ 361 阅读