在线认输。
自从我把妹子的学习之心给引起来之后,她的学习热情再也没下去过。这不,大早上就来找阿粉讨论算法。
妹子:小哥哥,我给你出个题啊
阿粉:来,我就不信能难到我
妹子:给定一个大小为 n 的数组,找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。 你可以假设数组是非空的,并且给定的数组总是存在多数元素。比如:数组 [3,2,3] 的多数元素是 3 ,数组 [2,2,1,1,1,2,2] 的多数元素是 2 。怎么样,可以答出来嘛?
阿粉:可真是小看我了。
阿粉略微思考了一下,既然多数元素在数组中出现的次数大于 ⌊ n/2 ⌋ ,我给这个数组排个序,然后取中间的值,得到的肯定就是多数元素,要不然不符合题意。
这样的话,两行代码就可以搞定:
1 |
|
阿粉写完程序之后,一运行一点儿毛病都没有,而且两行代码就搞定了,阿粉不由得骄傲起来
阿粉:小妹妹,我实现了,两行代码就搞定了。
妹子看了看,结果一脸嫌弃:你这样的代码简单是简单,但是时间复杂度是 O(nlogn) ,空间复杂度是 O(logn) ,应该还有更好的解决方案才对吧。
无奈阿粉的思路刚开始就是这样想的,所以怎么也想不到别的好办法了,就去请教妹子。
妹子:其实有个方案比你这个要好一点儿,就是摩尔投票法。咱们平时都是怎么投票的呢?大家每个人都选一个人写在纸条上,然后开始拆开纸团瞅瞅选的是谁。刚开始默认大家都是 0 票,然后纸条上投的是谁,这个人就多一票,最后看谁的票数比较多。回到咱们这个题目,既然是众数,而且出现的次数大于 ⌊ n/2 ⌋ ,那我们可以假设一个数就是要求的众数,同时设置这个数字出现的次数为 0 ,然后和接下来的数字进行比较。如果一样呢,咱们把这个数字出现的次数加上 1 ,如果不一样,就让次数减 1 ,当这个值减到 0 时,说明刚开始假设的数字不是众数,那就换当前的这个数字,继续循环。这样最后这个数字出现的次数一定是大于等于 0 的,要不然就不符合 出现的次数大于 ⌊ n/2 ⌋
这个题意了,最后的最后,将真正的众数返回即可。
阿粉:你这么一说,就把我的思路打开了,你等下,我这就去实现。
1 |
|
阿粉自己在内心小算盘了一下,发现这样的时间复杂度是 O(n) ,空间复杂度是 O(1) ,阿粉不由得在心里给妹子竖个大手指
让阿粉在线认输的操作,你会学会了嘛?