LeetCode 169. Majority Element
空でない配列の数がceiling(num.size()>>1)より大きい場合、次のシミュレーションが可能です.
配列の中の2つの異なる数を取って、それらを一緒に持って行って、このように一度に持って、最後に残った1つ(または同じいくつか)の数、つまりMajority Elementです.
コード:
配列の中の2つの異なる数を取って、それらを一緒に持って行って、このように一度に持って、最後に残った1つ(または同じいくつか)の数、つまりMajority Elementです.
コード:
class Solution
{
public:
int majorityElement(vector<int> &num)
{
int candidate;
int cnt = 0;
for (size_t i = 0; i < num.size(); ++ i)
{
if (cnt == 0)
{
candidate = num[i];
++ cnt;
} else
{
cnt += (candidate==num[i])? 1: -1;
}
}
return candidate;
}
};