leetcode 【 Majority Element 】python 实现

题目：

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.

代码：oj测试通过 Runtime: 197 ms

 class Solution:

     # @param num, a list of integers

     # @return an integer

     def majorityElement(self, num):

         if len(num) == 1:

             return num[0]

         candidate = 0

         count = 0

         for i in range(len(num)):

             if count == 0:

                 candidate = num[i]

                 count += 1

             else:

                 if num[i] == candidate :

                     count += 1

                 else:

                     count -= 1

         return candidate

思路：

这个自己想不出来。上网找的Moore Voting算法。

这个方法在思路上还是比较朴实无华的，但是很精妙。

注意题目的条件，重复出现大于数据长度一半的元素为众数。

因此可以采用一种对冲思路：一旦相邻的两个元素不同，就把这两个元素对冲抵消掉；由于众数的出现频次大于数据其他所有元素出现频次之和，所以这种对冲抵消最后剩下的一定是众数。

之前看过几篇日志说这道题还不错记录在下面：

http://www.yanyulin.info/pages/2014/12/851338983752.html

http://www.geeksforgeeks.org/majority-element/

http://bookshadow.com/weblog/2014/12/22/leetcode-majority-element/

巴特西

leetcode 【 Majority Element 】python 实现

最新文章

热门文章