作者:whisper
链接:https://www.proprogrammar.com/article/912
声明:请尊重原作者的劳动,如需转载请注明出处
数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。
你可以假设数组是非空的,并且给定的数组总是存在多数元素。
示例 1:
输入: [1, 2, 3, 2, 2, 2, 5, 4, 2] 输出: 2
限制:
1 <= 数组长度 <= 50000
难度:简单;标签:位运算,分治算法;编程语言:JAVA
class Solution {
// 题解中的一个比较好的方法
// https://leetcode-cn.com/problems/shu-zu-zhong-chu-xian-ci-shu-chao-guo-yi-ban-de-shu-zi-lcof/solution/onshi-jian-fu-za-du-o1kong-jian-fu-za-du-zhao-chu-/
public int majorityElement(int[] nums) {
int count = 1;
int res = nums[0];
for(int i = 1; i < nums.length; i++){
if(nums[i] == res){
count++;
}else{
count--;
if(count < 0){
count = 1;
res = nums[i];
}
}
}
return res;
}
}
自己想不到时间复杂度O(n)的解法,看一下题解中的解法,计数,遇到res结果数+1,其它数-1(抵消),当res<0时,重新计数,因为最终结果出现次数大于一半,所以最坏的情况下,最终结果的count也是大于0的,对其它的数,遇到不同的-1,肯定会减成<0,也就是说其它数会减成<0,而最终结果不论如何减,最终count都是大于0的,所以是可以的
亲爱的读者:有时间可以点赞评论一下
月份 | 原创文章数 |
---|---|
202204 | 1 |
202203 | 11 |
202201 | 2 |
202108 | 7 |
202107 | 3 |
202106 | 16 |
202105 | 10 |
202104 | 16 |
202103 | 56 |
202102 | 14 |
202010 | 3 |
202009 | 3 |
202008 | 7 |
202007 | 7 |
202006 | 10 |
202005 | 11 |
202004 | 22 |
202003 | 52 |
202002 | 44 |
202001 | 83 |
201912 | 52 |
201911 | 29 |
201910 | 41 |
201909 | 99 |
201908 | 35 |
201907 | 73 |
201906 | 121 |
201811 | 1 |
201810 | 2 |
201804 | 1 |
201803 | 1 |
201802 | 1 |
201707 | 1 |
全部评论