Leetcode: Majority Element
Leetcode: Majority Element
卡尔曼和玻尔兹曼谁曼
发布于 2019-01-25 14:43:58
发布于 2019-01-25 14:43:58
问题描述： 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.
方法一： 采用所谓的Moore voting algorithm： 每找出两个不同的element，就成对删除即count–，最终剩下的一定就是所求的。 C++示例代码：
int majorityElement(vector<int> &num)
{
int element = 0;
int count = 0;
for (vector<int>::iterator it = num.begin(); it != num.end(); it++)
{
if (count == 0)
{
element = *it;
count = 1;
}
else
{
if (element == *it)
{
count++;
}
else
{
count--;
}
}
}
return element;
}方法二： 随机挑选一个元素，检查是否是多数元素。 C++示例代码：
int majorityElement(vector<int> &num)
{
int count = 0;
int size = num.size();
if (size == 1)
{
return num[0];
}
while (true)
{
int index = rand() % size;
for (int i = 0; i < size; i++)
{
if (num[index] == num[i])
{
count++;
}
}
if (count > size / 2)
{
return num[index];
}
else
{
count = 0;
continue;
}
}
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2015年03月05日，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读