[剑指 Offer 第 2 版第 39 题] “数组中出现次数超过一半的数字”做题记录

第 39 题：数组中超过一半的数字

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

假设数组非空，并且一定存在满足条件的数字。

思考题：

假设要求只能使用 $O(n)$ 的时间和额外 $O(1)$ 的空间，该怎么做呢？

样例：

输入：[1,2,1,1,3]

输出：1

思路1：首先排序，中间那个数，一定是要求的。

思路2：将首次出现的数 count + 1，与之后的数进行比较，相等则 +1，否则 -1，最后进行校验是否超过长度的一半。数组中有一个数字出现的次数超过数组长度的一半，也就是说它出现的次数比其他所有数字出现次数的和还要多。因此我们可以考虑在遍历数组的时候保存两个值：一个是数组的一个数字，一个是次数。当我们遍历到下一个数字的时候，如果下一个数字和我们之前保存的数字相同，则次数加 $1$ ；如果下一个数字和我们之前保存的数字不同，则次数减 $1$ 。如果次数为零，我们需要保存下一个数字，并把次数设为 $1$ 。由于我们要找的数字出现的次数比其他所有数字出现的次数之和还要多，那么要找的数字肯定是最后一次把次数设为 $1$ 时对应的数字。

Python 代码：

  # -*- coding:utf-8 -*-
    class Solution:
        def MoreThanHalfNum_Solution(self, numbers):
            res = numbers[0]
            times = 1
            for num in numbers[1:]:
                if times == 0:
                    res = num
                    times = 1
                elif res == num:
                    times += 1
                else:
                    times -= 1
            # 验证 res 是不是超过一半
            times = 0
            for num in numbers:
                if num == res:
                    times += 1
            return res if times > len(numbers) // 2 else 0

说明：“假设数组非空，并且一定存在满足条件的数字。”的时候，就不用做最后一步的判断。

Python 代码：

  class Solution(object):
        def moreThanHalfNum_Solution(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """

            l = len(nums)
            if l == 1:
                return nums[0]

            num = nums[0]
            times = 1
            for i in range(1, l):
                # 注意分类讨论的顺序，先看次数是不是 0
                # 以下的 3 种情况是互斥的
                if times == 0:
                    num = nums[i]
                    times += 1
                elif num == nums[i]:
                    times += 1
                else:
                    times -= 1
            return num

C++ 代码：

Java 代码：

  import java.util.Arrays;

    public class Solution {
        //
        // {1,2,3,2,2,2,5,4,2} 9 4
        // {1,2,3,2,2,2,5,4} 8 4
        public int MoreThanHalfNum_Solution(int[] array) {
            int len = array.length;
            if (len == 0) {
                return 0;
            }
            Arrays.sort(array);
            int target = array[len / 2];
            int count = 0;
            for (int i = 0; i < len; i++) {
                if (array[i] == target) {
                    count++;
                }
            }
            if (count > len / 2) {
                return target;
            }
            return 0;
        }


        public static void main(String[] args) {
            int[] nums = new int[]{1, 2, 3, 2, 2, 2, 5, 4, 2};
            // [1,2,3,2,4,2,5,2,3]
            Solution solution = new Solution();
            int moreThanHalfNum_solution = solution.MoreThanHalfNum_Solution(nums);
            System.out.println(moreThanHalfNum_solution);
        }
    }