169._majority_element.md

###169. Majority Element

题目: https://leetcode.com/problems/majority-element/

难度: Easy

思路：

其实这个我有点有想到过

给定一个长度为 n的数组,其中有一个数，它出现的次数大于⎣n/2⎦，称为主要元素，找到它.

这个很像之前做过的一道CLRS的题目，想法可以用divide & conquer.

• 如果数组长度 <= 2,那么return第一个即解决问题
• 如果长度 > 2，那么可以两两配对，对于配对一样的结果，删去
  • 如果最后余一个，这一个留下
  • shuffle之后再尝试两两配对，直到最后结果不再改变

这样肯定是能解决问题的，因为为了满足次数大于⎣n/2⎦这个条件。

	 1 2        1 2          1 2         1 2
	 2 3        2 3          2 3         2 3
	 2          4 2          2 2         2 3
				2             4 2        3 3
										  3 2
										  2 2
										  2 2

思路容易implement非常难啊.

这个问题有一个很出名的算法

Boyer-Moore众数(majority number) 问题

在数组中找到两个不相同的元素并删除它们，不断重复此过程，直到数组中元素都相同，那么剩下的元素就是主要元素。

这个算法的妙处在于不直接删除数组中的元素，而是利用一个计数变量.

伪码

def majorityElement(self, nums):
    count,major=0,0
    for n in nums:
        if count==0:
            major=n
        if major==n:
            count+=1
        else:
            count-=1
    return major