我用两行代码搞定了,结果妹子有更巧妙的办法

在线认输。

自从我把妹子的学习之心给引起来之后,她的学习热情再也没下去过。这不,大早上就来找阿粉讨论算法。

妹子:小哥哥,我给你出个题啊

阿粉:来,我就不信能难到我

妹子:给定一个大小为 n 的数组,找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。 你可以假设数组是非空的,并且给定的数组总是存在多数元素。比如:数组 [3,2,3] 的多数元素是 3 ,数组 [2,2,1,1,1,2,2] 的多数元素是 2 。怎么样,可以答出来嘛?

阿粉:可真是小看我了。

阿粉略微思考了一下,既然多数元素在数组中出现的次数大于 ⌊ n/2 ⌋ ,我给这个数组排个序,然后取中间的值,得到的肯定就是多数元素,要不然不符合题意。

这样的话,两行代码就可以搞定:

1
2
Arrays.sort(nums);
return nums[nums.length >> 1];

阿粉写完程序之后,一运行一点儿毛病都没有,而且两行代码就搞定了,阿粉不由得骄傲起来

阿粉:小妹妹,我实现了,两行代码就搞定了。

妹子看了看,结果一脸嫌弃:你这样的代码简单是简单,但是时间复杂度是 O(nlogn) ,空间复杂度是 O(logn) ,应该还有更好的解决方案才对吧。

无奈阿粉的思路刚开始就是这样想的,所以怎么也想不到别的好办法了,就去请教妹子。

妹子:其实有个方案比你这个要好一点儿,就是摩尔投票法。咱们平时都是怎么投票的呢?大家每个人都选一个人写在纸条上,然后开始拆开纸团瞅瞅选的是谁。刚开始默认大家都是 0 票,然后纸条上投的是谁,这个人就多一票,最后看谁的票数比较多。回到咱们这个题目,既然是众数,而且出现的次数大于 ⌊ n/2 ⌋ ,那我们可以假设一个数就是要求的众数,同时设置这个数字出现的次数为 0 ,然后和接下来的数字进行比较。如果一样呢,咱们把这个数字出现的次数加上 1 ,如果不一样,就让次数减 1 ,当这个值减到 0 时,说明刚开始假设的数字不是众数,那就换当前的这个数字,继续循环。这样最后这个数字出现的次数一定是大于等于 0 的,要不然就不符合 出现的次数大于 ⌊ n/2 ⌋ 这个题意了,最后的最后,将真正的众数返回即可。

阿粉:你这么一说,就把我的思路打开了,你等下,我这就去实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 设置初始票数为 0
int count = 0 ;
// 先将要求的众数定义为空
Integer majorityElement = null;
	// 循环数组
    for(int num : nums){
		// 当 count 为 0 时,假设当前的数为要求的众数
        if (count == 0){
            majorityElement = num;
        }
		// 当 num 等于假设的众数时, count 就加 1
        count += ( num == majorityElement ) ? 1 : -1 ;
    }
// 最后返回真正的众数
return majorityElement;

阿粉自己在内心小算盘了一下,发现这样的时间复杂度是 O(n) ,空间复杂度是 O(1) ,阿粉不由得在心里给妹子竖个大手指

让阿粉在线认输的操作,你会学会了嘛?

Java Geek Tech wechat
欢迎订阅 Java 极客技术,这里分享关于 Java 的一切。