首页 > 编程语言 > 详细

leetcode 【 Majority Element 】python 实现

时间:2015-01-22 17:28:32      阅读:2944      评论:0      收藏:0      [点我收藏+]

题目

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

 1 class Solution:
 2     # @param num, a list of integers
 3     # @return an integer
 4     def majorityElement(self, num):
 5         if len(num) == 1:
 6             return num[0]
 7         
 8         candidate = 0
 9         count = 0
10         for i in range(len(num)):
11             if count == 0:
12                 candidate = num[i]
13                 count += 1
14             else:
15                 if num[i] == candidate :
16                     count += 1
17                 else:
18                     count -= 1
19         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 实现

原文:http://www.cnblogs.com/xbf9xbf/p/4241634.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!