Ex39 数组中出现次数超过一半的数字

题目描述

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。

解题思路

以下的代码很清晰明了就不再多做解释了。但是，这里说一个注意的点：

《剑指Offer》中的题目考虑到了找不到这么一个数的时候的情况，但是LeetCode上却没有。以LeetCode上的题目为准的话，最后需要确认一下，找到的数字是不是超过一半的。因为按照下面的思路，如果数组中有超过一半的数字，那么找到的数字，就一定是超过一半的数字；但如果数组中没有超过一半的数字，那么找到的数字就就肯定不是了。

代码

class Solution
{
public:
  int
  majorityElement (std::vector<int> &nums)
  {
    int num = nums[0], count = 1;
    for (int i = 1; i < nums.size (); ++i)
      {
        if (nums[i] == num)
          {
            ++count;
          }
        else
          {
            --count;
            if (count <= 0)
              {
                count = 1;
                num = nums[i];
              }
          }
      }
    return num;
  }
};

结果

执行结果：通过

执行用时：44 ms, 在所有 C++ 提交中击败了72.80%的用户

内存消耗：18.8 MB, 在所有 C++ 提交中击败了13.37%的用户