AcWing 52. 数组中出现次数超过一半的数字
宋标 Lv5
  2022-08-18 02:31:14 2022-08-18 02:31    

题目

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

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

思考题：

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

数据范围

数组长度 。

样例

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

输出：1

题解

空间O(N)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#define N 1010
int a[N];

class Solution {
public:

    int moreThanHalfNum_Solution(vector<int>& nums) {
        int n = nums.size();
        for (int i = 0; i < n; ++ i) ++ a[nums[i]];
        int half = n >> 1;
        for (int i = 0; i < N; ++ i)
            if (a[i] > half) return i;
    }
};

空间O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:

    int moreThanHalfNum_Solution(vector<int>& nums) {
        int val, cnt = 0;
        // O(1)空间复杂度的做法受限于出现次数严格要大于数组大小的一半
        for (auto x : nums)
        {
            if (!cnt) val = x, ++ cnt;
            else if (x == val) ++ cnt;
            else -- cnt;
        }
        return val;
    }
};
 评论