寻找多数元素-ag真人游戏

令a[1...n]是一个整数数列，a中的整数a如果出现的次数多于[n/2]，那么称a为多数元素。

有一个比较漂亮的求解法，我们用归纳法导出这个算法，这个算法的实质是基于下面的观察结论。

观察结论：在原序列中去除两个不同的元素后，那么原序列中的多数元素在新序列中还是多数元素。

其实就是遍历一遍，将互异的划掉。 

递归版：

    int candidate(vector<int>& nums, int m)
    {
        int j = m, n = nums.size(), cnt = 1, c = nums[m];
        while(j < n-1 && cnt > 0)
        {
            j  ;
            if(nums[j] == c) cnt  ;
            else cnt--;
        }
        if(j == n-1)  return c;
        else return candidate(nums, j 1);
    }
    int majorityelement(vector<int>& nums) {
        return candidate(nums, 0);
    }

非递归版：

    int majorityelement(vector<int>& nums) {
        int res, cnt = 0;
        for(int num: nums)
        {
            if(cnt == 0)
            {
                res = num; 
                cnt = 1;
            }
            else
            {
                if(num == res) cnt  ;
                else cnt--;
            }
        }
        return res;
    }

好像这也叫摩尔投票法（不清楚，反正我在课本上学的）

还有一种不错的解法，利用位运算，将这个大多数按位来建立，从0到31位，每次统计下数组中该位上0和1的个数，如果1多，那么将结果 res 中该位变为1，最后累加出来的 res 就是过半数了

    int majorityelement(vector<int>& nums) {
        int res = 0, n = nums.size();
        for (int i = 0; i < 32;   i) {
            int ones = 0, zeros = 0;
            for (int num : nums) {
                if (ones > n / 2 || zeros > n / 2) break;
                if (num & (1 << i))   ones;
                else   zeros;
            }
            if (ones > zeros) res |= (1 << i);
        }
        return res;
    }

另一种显然的方法就是利用map，这里可以使用unordered_map，其本质是哈希

    int majorityelement(vector<int>& nums) {
        unordered_map<int, int>mp;
        int n = nums.size();
        for(int i = 0;i < n;i  )
        {
            int tmp =   mp[nums[i]];
            if(tmp > n/2) return nums[i];
        }
        return -1;
    }