数组中出现次数超过一半的数

ryluo 2020-07-23 17:53:20

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

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

思考题

样例

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

输出:1

解法一:

使用哈希表,存下每个数字出现的次数,选出次数最多的那个数.时间复杂度和空间复杂度都为O(n)

class Solution {
public:
    int moreThanHalfNum_Solution(vector<int>& nums) {
        int max_num = 0;
        int res;
        unordered_map<int, int> mp;
        for(int i = 0; i < nums.size(); i++){
            auto iter = mp.find(nums[i]);
            if(iter != mp.end()){
                iter->second ++;
            }else{
                mp[nums[i]] = 1;
            }

            auto iter1 = mp.find(nums[i]);
            if(iter1->second > max_num){
                max_num = iter1->second;
                res = iter1->first;
            }
        }

        return res;
    }
};

解法二:

先对数组排序,中间位置的值就是众数,时间复杂度为O(NlogN),空间复杂度为O(1)

class Solution {
public:
    int moreThanHalfNum_Solution(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        return nums[int(nums.size() / 2)];
    }
};

解法三(最优解法):

这里需要注意,如果没有说明一定存在满足条件的数,还需要在得到结果之后再判断一次,该数超过的次数是否超过了一半.时间复杂度为O(n),空间复杂度为O(1)

class Solution {
public:
    int moreThanHalfNum_Solution(vector<int>& nums) {
        int cnt = 0;
        int val = 0;
        for(int i = 0; i < nums.size(); i++){
            if(cnt == 0){
                cnt = 1;
                val = nums[i];
            }else{
                if(val != nums[i]) cnt--;
                else cnt++;
            }
        }
        return val;
    }
};