Niuke.com: numbers that appear more than half of the times in the array

Catalog

Method 1 ： Hash

Method 2 ： Sort

Method 3 ： The candidate

---

Method 1 ： Hash

We can use a storage < Numbers , Number of occurrences > To determine whether a number appears more than half the time .

First traverse the output times , And then traverse to find the number of occurrences more than half .

The code is as follows ：

class Solution {
public:
    int MoreThanHalfNum_Solution(vector<int> numbers) {
        unordered_map<int, int> mp;
        for(const int n : numbers){
            mp[n]++;
        }
        for(const int val : numbers){
            if(mp[val]>numbers.size()/2){
                return val;
            }
        }
        return 0;
    }
};

Method 2 ： Sort

Because this number appears more than half of the time , So we sort it out , Then take the median .

The code is as follows ：

class Solution {
public:
    int MoreThanHalfNum_Solution(vector<int> numbers) {
        sort(numbers.begin(), numbers.end());
//         int cond=numbers[numbers.size()/2];
//         int cnt=0;
//         for(const int k : numbers){
//             if(cond==k) cnt++;
//         }
//         if(cnt > numbers.size()/2) return cond;
//         return 0;
        return numbers[numbers.size()/2];
    }
};

Because the problem is guaranteed to be solved , So we can directly return the median after sorting , If there is no guarantee of solvability , You also need to iterate through the array to see if the number of occurrences exceeds half .

O（nlogn） Time complexity of

Method 3 ： The candidate

This method is quite mysterious , Is to take the mode and other numbers to offset , The last remaining number is the number that we are looking for more than half of the times .

The code is as follows ：

class Solution {
public:
    int MoreThanHalfNum_Solution(vector<int> numbers) {
        int cond=-1;
        int cnt=0;
        for(int i=0;i<numbers.size();++i){
            if(cnt==0){
                cond=numbers[i];
                ++cnt;
            }else{
                if(cond==numbers[i]){
                    ++cnt;
                }else{
                    --cnt;
                }
            }
        }
        return cond;
    }
};