leetcode 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.

要求尋找數組中出現次數大于一半的某個元素。

思路：

1. 設目标元素為m，如果将原數組排序，由于m出現次數超過一半，那麼排序後索引為n/2的元素必定為m，這樣整個問題的複雜度為O(nlogn)+O(1)。

2. 由于m出現次數超過一半，如果每次從原數組中删除兩個不相等的元素（不管是否包含m），剩下的n-2個元素中，m的出現次數仍然超過一半。設n = 2*x+1，那麼最多執行x次删除兩個不等元素的操作，剩下的那個元素就是要找的m是以，我們可以根據這個結論，寫出複雜度O(n)的方法。

ps：可以參考《程式設計之美》中“尋找發帖水王”一題。

代碼（Java）：

public class Solution {
    public int majorityElement(int[] num) 
    {
        if(num.length <=2)
        {
            return num[0];
        }
        
        int count = 0;
        int candidate = num[0];
        for(int i = 0; i < num.length ; i++)
        {
           if(count == 0)
           {
               candidate = num[i];
               count++;
           }
           else
           {
               if(candidate==num[i])
               {
                   count++;
               }
               else
               {
                   count--;
               }
               
           }
        }
        
        return candidate;
    }
}
           

用一個例子 示範上面代碼的執行過程

設 數組中包含了 如下元素： A B B C D B E B B B C B B  （B出現次數超過一半）