Majority Element II

来源：Lintcode

原帖：http://www.lintcode.com/en/problem/majority-number-ii/

题目：
Given an array of integers, the majority number is the number that occurs more than 1/3 of the size of the array. Find it. Note: There is only one majority number in the array
Example: For [1, 2, 1, 2, 1, 3, 3] return 1. O(n) time and O(1) space

代码：

 class Solution {  
 public:  
   int computeTimes(const vector<int> &nums, int target) {  
     int count = 0;  
     for (const int &i : nums) {  
       if (i == target)   
         count++;  
     }  
     return count;  
   }  
   
   int majorityNumber(vector<int> nums) {  
     int candidate1 = 0, candidate2 = 0;  
     int count1 = 0, count2 = 0;  
     for (int i = 0; i < nums.size(); ++i) {  
       if (count1 == 0) {  
         if (count2 != 0 && candidate2 == nums[i]) {  
           count2++;  
         } else {  
           candidate1 = nums[i];  
           count1++;  
         }  
       } else {  
         if (candidate1 == nums[i]) {  
           count1++;      
         } else if (count2 == 0) {  
           count2++;   
           candidate2 = nums[i];  
         } else if (candidate2 == nums[i]) {  
           count2++;  
         } else {  
           count1--;   
           count2--;  
         }  
       }  
     }  
     if (count1 == 0) {  
       return candidate2;  
     } else if (count2 == 0) {  
       return candidate1;  
     } else {  
       return computeTimes(nums, candidate1) > computeTimes(nums, candidate2) ?   
         candidate1 : candidate2;  
     }  
   }  
 };