169. Majority Element

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.

#include <iostream> #include <vector> #include <algorithm> using namespace std; int majorityElement(vector<int>& nums) {     int m = nums[0];     int count = 1;     for(int i = 1; i < nums.size(); i++)  {         if(nums[i] == m)  {             count++;         } else  {             count--;//与该数的统计抵消          }         if(count < 0) //当count<0时 说明该数目前不能达到数目有n/2的要求 majority应至少剩余一个以上 {             m = nums[i];             count = 1;         }     }     return m; }

另记录下用hash的方法作为参考：[leetcode-169]Majority Element(java) - 博客频道 - .NET  http://blog.csdn.net/zdavb/article/details/47837017

public class Solution 

{

 public int majorityElement(int[] nums) {

HashMap<Integer,Integer> maps = new HashMap<>();

 int val = 0;

for(int i = 0;i<nums.length;i++){

val = nums[i];

if(!maps.containsKey(val))

maps.put(val,0);

int num = maps.get(val)+1;

maps.replace(val,num);

if(num>nums.length/2)

break;

}  

return val;

}

}