『剣指offer』NO 39配列に出現回数が半分を超える数字の詳細<Java実現>


//    :
    //                     ,       .
public class Solution
{
     
    //         .                 .            ans      .
    //     ,  ans         .
    //
    //
    //   ans              .

    /*  count==0,  now            , count   1;
      ,  now          , count++,  count–;
          ,       。*/
    public int MoreThanHalfNum_Solution(int[] nums)
    {
     
        int ans = 0;
        int cnt = 0;

        for (int num : nums)
        {
     
            //cnt  0             .
            if (cnt == 0)
            {
     
                ans = num;
                cnt = 1;
            }
            else if (ans == num)
            {
     
                cnt++;
            }
            else
            {
     
                cnt--;
            }
        }
        return ans;
    }
}