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出现次数超过一半）