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.

数组中出现次数超过一半的数字

C++(19ms):

 1 class Solution {
 2 public:
 3     int majorityElement(vector<int>& nums) {
 4         int len = nums.size() ;
 5         int res = nums[0] ;
 6         int times = 1 ;
 7         for (int i = 1 ; i < len ; i++){
 8             if (times == 0){
 9                 res = nums[i] ;
10                 times = 1 ;
11             }else if (res == nums[i]){
12                 times++ ;
13             }else{
14                 times-- ;
15             }
16         }
17         times = 0 ;
18         for(int i = 0 ; i < len ; i++){
19             if (res == nums[i])
20                 times++ ;
21         }
22         if (times*2 <= len)
23             res = 0 ;
24         return res ;
25     }
26 };