面试题39

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

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例 1:

输入: [1, 2, 3, 2, 2, 2, 5, 4, 2]
输出: 2

限制：

• 1 <= 数组长度 <= 50000

注意：本题与主站 169 题相同：https://leetcode-cn.com/problems/majority-element/

Solutions

1. deduce and conquer

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int cur = INT_MIN, len = 0;
        for (auto n : nums) {
            if (len == 0)
                cur = n;
            len += n == cur ? 1 : -1;
        }
        return cur;
    }
};

1. devide and conquer

class Solution {
public:
    int majority(vector<int> & nums, int lo, int hi) {
        if (hi - lo == 1) return nums[lo];
        int mid = lo + ((hi - lo) >> 1);
        int left = majority(nums, lo, mid);
        int right = majority(nums, mid, hi);
        if (left == right) return left;
        else {
            auto begin = nums.begin();
            int lcnt = count(begin + lo, begin + hi, left);
            int rcnt = count(begin + lo, begin + hi, right);
            return lcnt > rcnt ? left : right;
        }
    }
    int majorityElement(vector<int>& nums) {
        return majority(nums, 0, nums.size());
    }
};