题目描述 
分析 该题有多种解法，我们一个个来看。
最笨最直接的一种，就是我对数据的每个元素挨个挨个的去遍历求出它的出现次数，最后，取出现次数最高的那个即为所求。 代码如下：
int majorityElement(int* nums, int numsSize) {int count[numsSize];int max=0,maxindex;for(int i=0;i<numsSize;i++) count[i]=0;for(int i=0;i<numsSize;i++){ for(int j=0;j<numsSize;j++){ if(nums[i]==nums[j]) count[i]+=1; }}for(int i=0;i<numsSize;i++){ if(count[i]>max){ maxindex=i; max=count[i]; }}return nums[maxindex];}遗憾的是，从代码中也可看出，‘重复性’计算很多，该方法并不高效。
法二： 我们注意看题干，找出的出现次数最多的元素是半数以上的，注意关键词，半数以上。 这便让我想到了Moore’s voting algorithm。 该算法解决的问题，正是从一个数组中找出出现半数以上的元素。 代码如下：
int majorityElement(int* nums, int numsSize) {int majorityIndex = 0;int count=1;for (int i = 1; i < numsSize; i++) { nums[majorityIndex] == nums[i] ? count++ : count--; if (count == 0) { majorityIndex = i; count = 1; }}return nums[majorityIndex];}该算法只有O（n）的复杂度，特别的精练。
法三: 因为是出现半数以上的，那么我们对数组排序后，最中间的那个元素值即为所求。 这里就不写代码了。像C++，python等语言，我们可以直接调用库里的sort函数。
法四: 使用分而治之的思想。我们把数组分成左右两块，每次都找寻出现次数最多的元素。终止条件是，数组中只剩一个元素了，那么就返回该元素。 代码如下：(不想自己写计算数组中某元素出现次数的函数，于是就用了C++来写）
class Solution {public:int majorityElement(vector<int>& nums) { return findmajority(nums, 0, nums.size() - 1);}PRivate:int findmajority(vector<int>& nums, int left, int right) { if (left == right) return nums[left]; int mid = left + (right - left)/2; int lmajor = findmajority(nums, left, mid); int rmajor = findmajority(nums, mid + 1, right); if (lmajor == rmajor) return lmajor; if(count(nums.begin() + left, nums.begin() + right + 1, lmajor) > count(nums.begin() + left, nums.begin() + right + 1, rmajor)) return lmajor; else return rmajor;}};法五: 该方法是我之前没有想到的，Bit Manipulation，很机智的一种方法。从位的角度去理解，一个元素在数组中出现半数以上造成的影响。 代码如下：
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;} };新闻热点
疑难解答
