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

 

思路：

　　找到一个数组中出现次数超过一半的数。排序、哈希等方法就不提了，考虑O(n)的复杂度，有一种传说中的摩尔投票算法可用。其实也很简单，初始选第一个元素，依次比对它和其它的元素，若相等则其票数加一，反之则减一，当其票数为0时，更换投票对象为当前的元素，继续执行，最终即可得结果（前提的数组中存在这样的数，否则结果不确定是什么，依赖于元素的摆放顺序）。

C++:

1 class Solution { 2 public: 3 int majorityElement(vector<int> &num) { 4 5 int len = num.size(); 6 if(len == 0) 7 return 0; 8 9 int cnt = 0, ret = num[0]; 10 for(int i = 0; i < len; i++) 11 { 12 if(cnt == 0) 13 { 14 ret = num[i]; 15 cnt++; 16 } 17 else 18 { 19 if(num[i] == ret) 20 cnt++; 21 else 22 cnt--; 23 } 24 } 25 return ret; 26 } 27 };

 

Python:

1 class Solution: 2 # @param {integer[]} nums 3 # @return {integer} 4 def majorityElement(self, nums): 5 ret, cnt = 0, 0 6 7 for val in nums: 8 if cnt == 0: 9 ret = val 10 cnt = 1 11 else: 12 if ret == val: 13 cnt = cnt + 1 14 else: 15 cnt = cnt - 1 16 return ret 17

 

转载于:https://www.cnblogs.com/tjuloading/p/4614397.html

总结

以上是生活随笔为你收集整理的【LeetCode 169】Majority Element的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。