LeetCode 169. Majority Element

600 ワード

空でない配列の数がceiling(num.size()>>1)より大きい場合、次のシミュレーションが可能です.
配列の中の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;
    }
};