《剑指offer》python： 39 数组中出现次数超过一半的数字

Bertha 。 2022-05-17 07:55 124阅读 0赞

## 题目 ##

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。  
例如输入一个长度为9的数组\{1,2,3,2,2,2,5,4,2\}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。**如果不存在则输出0**。

**思路1 ：快速排序，求中位数。**  
如果该数出现次数超过数组长度的一半，那么，排序之后，他应该位于数组的中间，即为中位数。  
具体操作：随机选一数，快排一次。如果该数位于数列正中间，则正好是中位数。如果该数位于数列中间偏左，则中位数位于该数右侧，在右侧区域重新选一数快排一次。直至找到中位数。  
复杂度：O(n)

**思路2：保存两个数值：保存的数字 + 其出现的次数**  
根据数组的特点，出现次数超过一半的数，他出现的次数比其他数字出现的总和还要多，因此可以最开始保存两个数值：数组中的一个数字以及它出现的次数，然后遍历，如果下一个数字等于这个数字，那么次数加一，如果不等，次数减一，当次数等于0的时候，在下一个数字的时候重新复制新的数字以及出现的次数置为1，直到进行到最后，然后再验证最后留下的数字是否出现次数超过一半，因为可能前面的次数依次**抵消掉**，最后一个数字就直接是保留下来的数字，但是出现次数不一定超过一半。  
复杂度：O(n)

**思路3：（传统思路）建立个字典，统计各数字次数**

--------------------

#### 思路1的代码 ####

暂缺

#### 思路2的代码 ####

class Solution:
        def MoreThanHalfNum_Solution(self, numbers):
            count = 1
            number = numbers[0]
            for i in numbers[1:]:
                if number == i:
                    count += 1
                else:
                    count -= 1
                    if count == 0:
                        number = i
                        count += 1
            # 至此选出一个数，但不一定次数过半。最后再迭代一轮，为其记个数。
            sum = 0
            for j in numbers:
                if j == number:
                    sum += 1
    
            return number if sum > len(numbers) // 2 else 0

运行时间：21ms  
占用内存：5732k

#### 思路3的代码 ####

class Solution:
        def MoreThanHalfNum_Solution(self, nums):
            Num_Count = dict() # key：value -> 数字：次数
            length = len(nums)
            for n in nums:
                Num_Count[n] = Num_Count[n] + 1 if Num_Count.get(n) else 1
                if Num_Count[n] > length / 2:
                    return n
            return 0

运行时间： 20 ms  
占用内存：5736K

--------------------

运行环境： 牛客网