看到这道题，很多应聘者就会想要是这个数组是排序的数组就好了。 如果是排好序的数组，那么我们就能很容易统计出每个数字出现的次数。题目给出的数组没有说是排序的，因此我们需要先给它排序。排序的时间复杂度是\(O(nlogn)\)。最直观的算法通常不是面试官满意的算法，接下来我们试着找出更快的算法，空间复杂度更小的算法。

Question

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。 你可以假设数组是非空的，并且给定的数组总是存在多数元素。

 示例 1:

输入: [1, 2, 3, 2, 2, 2, 5, 4, 2]
输出: 2

限制：1 <= 数组长度 <= 50000

测试用例

功能测试（输入的数组中存在一个出现次数超过数组长度一半的数字；输入的数组中不存在一个出现次数超过数组长度一半的数字）。 特殊输入测试（输入的数组中只有一个数字；输入 nullptr 指针）。

本题考点

考查应聘者对时间复杂度的理解。应聘者每想出一种解法，面试官都期待他能分析出这种解法的时间复杂度是多少。 考查应聘者思维的全面性。面试官除了要求应聘者能对有效的输入返回正确的结果，同时也期待应聘者能对无效的输入进行相应的处理。

Intuition

额外空间

使用额外空间进行出现次数统计，即可实现时间复杂度为 \(O(n)\) 的算法，空间复杂度为 \(O(n^2)\)，需要一个 \(n \times 2\) 的矩阵，\(n\) 为输入数组中的数字类型数，例如 nums=[1, 2, 3, 1, 2, 3, 1, 1, 1, 1, 1,]，\(n=3\)。

类快排算法

数组中有一个数字出现的次数超过了数组长度的一半。如果把这个数组排序，那么排序之后位于数组中间的数字一定就是那个出现次数超过数组长度一半的数字。也就是说，这个数字就是统计学上的中位数，即长度为n的数组中第n/2大的数字。 这种算法受快速排序算法的启发。在随机快速排序算法中，我们 1. 先在数组中随机选择一个数字，2. 然后调整数组中数字的顺序，使得比选中的数字小的数字都排在它的左边，比选中的数字大的数字都排在它的右边。 3. 如果这个选中的数字的下标刚好是n/2，那么这个数字就是数组的中位数；4. 如果它的下标大于n/2，那么中位数应该位于它的左边，我们可以接着在它的左边部分的数组中查找；5. 如果它的下标小于n/2，那么中位数应该位于它的右边，我们可以接着在它的右边部分的数组中查找。这是一个典型的递归过程。时间复杂度为 \(O(n)\)，空间复杂度为 \(O(1)\)。

基于数组特点的方法（best method）

数组中有一个数字出现的次数超过数组长度的一半，也就是说它出现的次数比其他所有数字出现次数的和还要多。因此，我们可以考虑在遍历数组的时候保存两个值：一个是数组中的一个数字；另一个是次数。 1. 当我们遍历到下一个数字的时候，如果下一个数字和我们之前保存的数字相同，则次数加1； 2. 如果下一个数字和我们之前保存的数字不同，则次数减1。3. 如果次数为零，那么我们需要保存下一个数字，并把次数设为1。由于我们要找的数字出现的次数比其他所有数字出现的次数之和还要多，那么要找的数字肯定是最后一次把次数设为1时对应的数字。时间复杂度为 \(O(n)\)，空间复杂度为 \(O(1)\)，且易于理解。

Code

• 基于额外空间的方法

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        if len(nums) < 2:  return nums[0]
        n = len(nums) // 2
        hash_map = {}
        for i in nums:
            if i in hash_map:
                hash_map[i] += 1
                if hash_map[i] > n:
                    return i
            else:
                hash_map[i] = 1
                

• 类快排算法

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        _len = len(nums)
        # 特判不正确输入的nums
        if not self.checkValid(nums, _len):
            return 0  # 输入不合法就返回0
        # 特判输入长度为1的nums
        if _len == 1:
            return nums[0]
        
        middle = _len >> 1  # 等效于 _len // 2
        start = 0
        end = _len - 1
        index = self.partition(nums, _len, start, end)
        while index != middle:
            if index > middle:
                end = index - 1
                index = self.partition(nums, _len, start, end)
            else:
                start = index + 1
                index = self.partition(nums, _len, start, end)

        # result = nums[middle]  # while循环结束的条件就是 index == middle
        result = nums[index]  # 所以这里写 result = nums[middle] 或者 result = nums[index]都可以

        if not self.checkResult(nums, _len, result):
            result = 0
        return result


    # 划分函数，只进行一次二分查找，不递归。
    def partition(self, nums, _len, start, end):
        if nums == None or _len < 1 or start < 0 or end >= _len:
            return None
        if end == start:
            return end
        pivotvlue = nums[start]
        leftmark = start + 1
        rightmark = end

        done = False
        # 开始将小于pivotvlue的元素移到右边，大于pivotvlue的元素移到左边。
        while not done:
            # 从左向右找到一个大于pivotvlue的元素
            # leftmark <= rightmark必须放到nums[leftmark] <= pivotvlue前面
            while leftmark <= rightmark and nums[leftmark] <= pivotvlue:
                leftmark += 1
            # 从右向左找到一个小于pivotvlue的元素
            while rightmark >= leftmark and nums[rightmark] >= pivotvlue:
                rightmark -= 1
            # 交换这两个元素
            if leftmark > rightmark:
                done = True
            else:
                nums[leftmark], nums[rightmark] = nums[rightmark], nums[leftmark]
        nums[rightmark], nums[start] = nums[start], nums[rightmark]
        return rightmark


    # 检查输入nums是否合法
    def checkValid(self, nums, _len):
        is_valid = True
        if nums == None or _len < 1:
            is_valid = False
        return is_valid

    # 检查结果是否是众数
    def checkResult(self, nums, _len, result):
        count = 0
        for i in range(_len):
            if nums[i] == result:
                count += 1
        if count * 2 <= _len:
            return False
        return True

此方法在接收LeetCode的超长输入样例时会超时。

• 基于数组特点的方法

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        _len = len(nums)
        if not self.checkValid(nums, _len):
            return 0  # 输入不合法就返回0
        result = nums[0]
        times = 1
        for i in range(1, _len):
            if times == 0:
                result = nums[i]
                times = 1
            elif nums[i] == result:
                times += 1
            else:
                times -= 1
    
        if not self.checkResult(nums, _len, result):
            result = 0
        return result

    # 检查输入nums是否合法
    def checkValid(self, nums, _len):
        is_valid = True
        if nums == None or _len < 1:
            is_valid = False
        return is_valid

    # 检查是否是众数
    def checkResult(self, nums, _len, result):
        count = 0
        for i in range(_len):
            if nums[i] == result:
                count += 1
        if count * 2 <= _len:
            return False
        return True