NumMoreThanHalf

发表于 更新于 分类于

题目描述[][][原题链接][https://www.acwing.com/problem/content/description/48/]

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。

假设数组非空，并且一定存在满足条件的数字。

思考题：

  • 假设要求只能使用 O(n)O(n) 的时间和额外 O(1)O(1) 的空间，该怎么做呢？

样例

1
2
3
输入：[1,2,1,1,3]

输出：1

算法描述

初始化变量，假设过半的树就是数组的第一个元素，个数为0,遍历数组，如果当前数组的值等于当前节点的值，计数器加1，如果计数器小于0，更新结果，直到遍历完数组

C++代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int moreThanHalfNum_Solution(vector<int>& nums) {
        int cnt=0,val=-1;
        for(auto x:nums){
            if(x==val){
                cnt++;
            }else {
                if(cnt)cnt--;
                else {
                    cnt=1;
                    val=x;
                }
            }
        }
        return val;
    }
};

Java代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int moreThanHalfNum_Solution(int[] nums) {
        int x = nums[0],ans = 0;
        for(int i=0;i<nums.length;i++){
            if(nums[i]!=x){
                ans--;
                if(ans<0){
                    x = nums[i];
                    ans = 1;
                }
            }else ans++;
        }
        return x;
    }
}