Leetcode.169.Majority Element

题目

给定一个非空长度为n的数组, 数组中有一个数超过n/2, 输出该数.

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

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

思路1

通过map记录每个数出现的次数.
容易实现, 时间复杂度一般, 空间复杂度太高.

int majorityElement(vector<int>& nums) {
    if (nums.empty()) return 0;

    unordered_map<int, int> map;
    int max = 0;
    int res = nums[0];
    for(int a : nums) {
        if (map.count(a) == 0) {
            map[a] = 1 ;
        } else {
            map[a] += 1;
        }
        if (map[a] > max) {
            max = map[a];
            res = a;
        }
    }
    return res;
}

思路2

排序, 超过一般的数肯定在排序数组的中间位置.

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

思路3

双指针, 一个前指针, 一个后指针.
如果两个指针的数不一样, 就将两个数都置为INT_MIN. 最后剩下不为INT_MIN的即为出现超过一半的数.

int majorityElement(vector<int>& nums) {
    if (nums.empty()) return 0;
    for(int i = 0, j = 1; j < nums.size();) {
        while (nums[i] == INT_MIN) {
            i++;
        }
        if (nums[i] != nums[j]) {
            nums[i++] = INT_MIN;
            nums[j++] = INT_MIN;
        }else {
            j++;
        }
    }
    for(int a : nums) {
        if (a != INT_MIN) {
            return a;
        }
    }
    return nums[0];
}

总结

出现超过一半的数比较特殊, 利用双指针, 将不一样的元素忽略掉, 最后剩下的即为结果.