剑指28-数组中出现次数超过一半的数字

Posted on | In |

题目描述

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

  • 遍历数组，用字典统计数字的频率，一旦某个数字的频数大于数组长度的一半，则返回该数。
  • 如果遍历数组过程中没有返回，则说明没有数字频数大于数组长度的一半，返回0。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def MoreThanHalfNum_Solution(self, numbers):
        # write code here
        log = {}
        half = len(numbers)/2.0
        if half == 0:
            return 0
        if half == 0.5:
            return numbers[0]
        for num in numbers:
            if log.has_key(num):
                log[num] += 1
                if log[num] > half:
                    return num
            else:
                log[num] = 1
        return 0

用字典的时间效率是O(n)，但空间效率不占有，而空间效率是O(1)的算法是存在的。

  • 遍历数组时保存两个值，一个是数组中的一个数字，一个是次数。
  • 每遍历到一个数字，如果该数字与所保存值相等，次数加1；不相等则次数减去1；如果次数已经为0且不相等，则将保存值更新为该数字，次数置为1。
  • 如果存在出现次数超过一半的数字，则必定是最后的保存值。由于是必要条件，所以程序中要确认该值是否真的出现了超过一半的次数，即至少为(len(numbers)>>1)+1。

分析原理：数组长度为N，最后的次数值是M，则M<=N，由于次数值一直都是非负数，那么可知有2*(N-M)个数在加减运算中两两抵消掉了。而出现一半的数字肯定不会全被抵消掉。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def MoreThanHalfNum_Solution(self, numbers):
        log = [0, 0]
        for num in numbers:
            if num == log[0]:
                log[1] += 1
            else:
                if log[1] == 0:
                    log[0], log[1] =  num, 1
                else:
                    log[1] -= 1

        half = (len(numbers)>>1)+1 # 一半加一
        for num in numbers:
            if num == log[0]:
                half -= 1
        if half <= 0:
            return log[0]
        else:
            return 0

partition函数法。

  • 快排的partition函数能够以某个数为基准，将数组内元素按大小分为小于该数和大于等于该数两部分。可以用来将数组分成前k个较小值和其余的值两部分，方法是迭代，将partition函数的输入区间向k和拢。
  • 而出现次数超过一半的数，排序之后肯定会在下标len(numbers)>>1上出现，因此用partition函数找到该数，然后检查其是否满足条件即可。
  • 每次迭代使得partition的输出更接近len(numbers)>>1这个下标，直到二者相等。如果有出现次数超过一半的数，则必然是该下标的元素。究竟是不是，也要检查一番才能确定。
  • 注意：虽然partition的输出下标左侧的元素肯定要小于该下标所指的元素，但最终len(numbers)>>1这个下标左侧的元素却是小于等于该下标所指元素。只是由while True循环里对s和t的更新方式导致的。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution:
    def MoreThanHalfNum_Solution(self, numbers):
        def partition(nums, l, r):
            x = nums[r]
            i, j = l, r-1
            while i < j: 
                while nums[i] < x and i < j: # 循环终止时i满足nums[i]>=x或者i==j
                    i += 1
                while nums[j] >= x and i < j: # 循环终止时j满足nums[j]<x或者i==j
                    j -= 1
                if j > i: # 说明必有nums[i]>=x且nums[j]<x，需要调换二者位置
                    nums[i], nums[j] = nums[j], nums[i]
            if nums[i] < x: 
                i += 1
            nums[i], nums[r] = x, nums[i] 
            return i
        
        def checkMoreThanHalf(num, numbers):
            half = (len(numbers)>>1)+1 # 一半加一
            for n in numbers:
                if n == num:
                    half -= 1
            return half <= 0
        if len(numbers) == 0:
            return 0
        s, t = 0, len(numbers)-1
        mid = len(numbers)>>1
        while True:
            ix = partition(numbers, s, t) 
            if ix > mid:
                t = ix - 1
            elif ix < mid: 
                s = ix + 1
            else:
                break
        num = numbers[mid]
        return num if checkMoreThanHalf(num, numbers) else 0