Cacher is the code snippet organizer for pro developers

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int temp;
        
        sort(nums.begin(),nums.end());
        
        // for(int i = 0;i < nums.size();++i)
        //     cout << nums[i] << " ";
        // cout << endl;
        // cout << nums.size() << endl;
        // cout << floor(nums.size() / 2);
        
        for(int i = 0;i < nums.size() - 1;++i){
            if(nums[i] == nums[i+1]){
                temp++;
                cout << temp << " ";
                if(temp >= floor(nums.size() / 2))
                    return nums[i];
            }
            else
                temp = 0;
        }
        return 100;
    }
};

//在这使用STL排序方法
//注意的是，虽然后面思想相同，但使用不同的排序语句，效率有很大差别

//第一种：Runtime: 16 ms, faster than 68.72%

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

//第二种：Runtime: 12 ms, faster than 98.44%

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

//一种全新的方法，完全不懂，但效率提升非常高！

//未加上<ios>库之前 Runtime: 16 ms, faster than 68.72%
  
class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int cnt = 1,majIdx = 0;
        
        for(int i = 1;i < nums.size();++i){
            if(nums[i] == nums[majIdx])
                ++cnt;
            else
                --cnt;
            if(!cnt)
                majIdx = i,cnt = 1;
        }
        return nums[majIdx];
    }
};

//加上之后  Runtime: 8 ms, faster than 99.37%

#include <ios>
static auto fastInput = []() {
    ios_base::sync_with_stdio(false),cin.tie(nullptr);
    return 0;
}();

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

//使用哈希表建立字典进行查询
//Runtime: 20 ms, faster than 50.07% 
class Solution {
public:
    int majorityElement(vector<int>& nums) {
        unordered_map<int,int> counts;
        int n = nums.size();
        for(int i = 0;i < n;++i){
            if(++counts[nums[i]] > n/2)
                return nums[i];
        }
    }
};

//使用随机数来进行比较，因为题目比较特殊
//使用随机数方式可以很快猜出最大数
//Runtime: 16 ms, faster than 69.67%

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int n = nums.size();
        srand(unsigned(time(NULL)));
        while(true){
            int idx = rand() % n;
            int candidate = nums[idx];
            int counts = 0;
            for(int i = 0;i < n;++i)
                if(nums[i] == candidate)
                    counts++;
            if(counts > n/2) return candidate;
        }
    }
};

//使用分治法
//思想比较复杂，重点在于初始结构的建立
//Runtime: 20 ms, faster than 50.07%

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        return majority(nums,0,nums.size() - 1);
    }
private:
    int majority(vector<int>& nums,int left,int right){
        if(left == right) return nums[left];
        int mid = left + ((right - left) >> 1);
        int lm = majority(nums,left,mid);
        int rm = majority(nums,right,mid);
        int (lm == rm) return lm;
        return count(nums.begin() + left,nums.begin() + right + 1,lm) > count(nums.begin() + left,nums.begin() + right + 1,rm) ? lm : rm;
    }
    
};

//使用摩尔投票法，这种思想之前好像遇见过
//Runtime: 16 ms, faster than 69.67%

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int major,counts = 0,n = nums.size();
        for (int i = 0;i < n;++i){
            if(!counts){
                major = nums[i];
                counts = 1;
            }
            else counts += (nums[i] == major) ? 1 : -1;
        }
        return major;
    }
};

//真的是很新奇的方法，使用位运算来进行求解
//Runtime: 24 ms, faster than 30.40%

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int major = 0,n = nums.size();
        for(int i = 0,mask = 1;i < 32;i++,mask <<= 1){
            int bitCounts = 0;
            for(int j = 0;j < n;j++){
                if(nums[j] & mask) bitCounts++;
                if(bitCounts > n/2){
                    major |= mask;
                    break;
                }
            }
        }
        return major;
    }
};