LeetCode刷算法题 - 169. Majority Element

写在前面:

程序员分两种，会算法的程序员和不会算法的程序员。几乎没有一个一线互联网公司招聘任何类别的技术人员是不考算法的，程序猿们都懂的，现在最权威流行的刷题平台就是 LeetCode。

Question:

Difficulty:Easy Tag:Array

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

You may assume that the array is non-empty and the majority element always exist in the array.

Example:

Input: [3,2,3]
Output: 3

Input: [2,2,1,1,1,2,2]
Output: 2

Solution:

以下代码皆是本人用 C++写的，觉得还不错的话别忘了点个赞哦。各位同学们如果有其他更高效解题思路还请不吝赐教，多多学习。

A1、运用哈希特性

运用哈希map 的不重复性质循环遍历数组
以数组元素为 key，value 为相同数字key 的个数
当统计出value>n/2，此时元素key 为众数。

算法时间复杂度 O(n)，Runtime: 16 ms，代码如下

int x=[](){
    std::ios::sync_with_stdio(false);  //关闭STDIN和CIN同步 减少CIN读入的时间，可以减少50%以上。
    cin.tie(NULL);
    return 0;
}();

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        map<int,int> map;
        
        for (int i=0; i<nums.size(); i++) {
            int key = nums[i];
            if (map.find(key) == map.end()) {
                map[key] = 1;
            } else{
                map[key] = map[key]+1;
            }
            if (map[key] > nums.size()/2) {
                return nums[i];
            }
        }
        return 0;
    }
};

A2、渐进排除式解法

突出运用众数个数大于 n/2的特征
即 众数个数 - 其他所有数个数 > 0
换句话 任意一个数个数 - 其他所有数个数 < 0
则此数排除，剩下的就是众数

算法时间复杂度 O(n)，Runtime: 10 ms，代码如下

int x=[](){
    std::ios::sync_with_stdio(false);  //关闭STDIN和CIN同步 减少CIN读入的时间，可以减少50%以上。
    cin.tie(NULL);
    return 0;
}();

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

    }
};

引用相关

LeetCode 官网