问题描述: 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;
}
}
}