百度蜘蛛抓取网站,网站建设模板软件,阿里云网站建设考试认证题,标准物质网站建设模板题目
数组中占比超过一半的元素称之为主要元素。给你一个 整数 数组#xff0c;找出其中的主要元素。若没有#xff0c;返回 -1 。请设计时间复杂度为 O(N) 、空间复杂度为 O(1) 的解决方案。
示例 1#xff1a;
输入#xff1a;[1,2,5,9,5,9,5,5,5] 输出#xff1a;5 …题目
数组中占比超过一半的元素称之为主要元素。给你一个 整数 数组找出其中的主要元素。若没有返回 -1 。请设计时间复杂度为 O(N) 、空间复杂度为 O(1) 的解决方案。
示例 1
输入[1,2,5,9,5,9,5,5,5] 输出5 示例 2
输入[3,2] 输出-1 示例 3
输入[2,2,1,1,1,2,2] 输出2
解题思路
摩尔投票理解
对于[1,2,5,9,5,9,5,5,5]主要元素为5可以想象成元素被分成了两拨一波是主要元素一波是非主要元素。 假设元素之间两两相互抵消
在最坏的情况下所有非主要元素和主要元素两两相互抵消最后应该会剩下一个主要元素在最好情况下非主要元素之间互相残杀先把非主要元素内部的元素尽量抵消掉然后再去与主要元素抵消最后剩下的主要元素1所以即使在最坏的情况下仍然最少会剩下一个主要元素的所以我们假设主要元素是cancnt代表can元素与非主要元素抵消后can元素还剩多少个当cnt0时说明当前的can元素已经被全部抵消掉了需要重新设定新的can元素因为使用can记录了当前主要元素所以可以防止相同元素之前互相残杀
代码
class Solution {public int majorityElement(int[] nums) {int can-1,cnt0,res0;for (int num : nums) {if(cnt0){cannum;}if(numcan){cnt;}else {cnt--;}}for (int num : nums) {if(numcan)res;}return res(int)(Math.floor((double)nums.length/2)1)?can:-1;}
}
