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

Find k different element, and “remove” them as a group, the remaining element must be the element that appears more than ⌊n/k⌋ times. (Detailed explanation is given in comment)

In this problem, k equals to 2.

Thus we “remove” each pair of 2 different elements, and the remaining element that do not have its counterpart is the desired element.

如果f(c)为0，表示当前并没有候选元素，也就是说之前的遍历过程中并没有找到超过半数的元素。那么，如果超过半数的元素c存在，那么c在剩下的子数组中，出现次数也一定超过半数。因此我们可以将原始问题转化为它的子问题。此时c赋值为当前元素, 同时f(c)=1。



http://m.blog.csdn.net/blog/wenyusuran/40780253

class Solution {
public:
int majorityElement(vector<int>& nums)
{
int size = nums.size();
int vote = 0;
int count = 0;

for(int i = 0;i < size;i++)
{
if(count == 0)
{
vote = nums[i];
count = 1;
}
else
{
if(vote == nums[i])
count++;
else
count--;
}
}
return vote;
}
};

STL解决方案：

int majorityElement(vector<int> &num)
{
map<int, int>count;
for (vector<int>::iterator i = num.begin(); i != num.end();i++)
{
if ( (++count[*i]) > num.size() / 2)
return *i;

}
}


c语言：

int majorityElement(int num[], int n)
{
int cnt = 0, res;
for (int i = 0; i < n; ++i)
{
if (cnt == 0) res = num[i];
if (res == num[i]) ++cnt;
else --cnt;
}
return res;
}



python解决方案：

class Solution:
# @param {integer[]} nums
# @return {integer}
def majorityElement(self, nums):
count = {}
for i in nums:
if i not in count:
count[i] = 0
count[i] += 1
if count[i] > len(nums)/2:
return i


|
3月前
|
SQL
leetcode-SQL-1211. 查询结果的质量和占比
leetcode-SQL-1211. 查询结果的质量和占比
25 0
|
3月前
|
SQL
leetcode-SQL-1141. 查询近30天活跃用户数
leetcode-SQL-1141. 查询近30天活跃用户数
34 0
|
3月前
|

map|二分查找|离线查询|LeetCode:2736最大和查询
map|二分查找|离线查询|LeetCode:2736最大和查询
42 0
|
3月前
|

map|二分查找|离线查询|LeetCode:2736最大和查询
map|二分查找|离线查询|LeetCode:2736最大和查询
43 0
|
9月前
Leetcode 230. Kth Smallest Element in a BST

54 1
|
Python
LeetCode 378. Kth S Element in a Sorted Matrix

86 0
|

LeetCode 229. Majority Element II

71 0
|

LeetCode 162. Find Peak Element

86 0
|

LeetCode 169. 多数元素 Majority Element
LeetCode 169. 多数元素 Majority Element
78 0
LeetCode 215. Kth Largest Element in an Array

68 0