【剑指offer】数组中出现次数超过数组长度一半的数字（三种解法）

121 阅读 0 评论 80 点赞

我是靠谱客的博主包容便当，这篇文章主要介绍【剑指offer】数组中出现次数超过数组长度一半的数字（三种解法），现在分享给大家，希望可以做个参考。

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

如果使用时间复杂度为O(n),可以构建hash map，但是应该会存在冲突，并且要设计数据结构
在python3中，如果要让map输出list，在前面要加list，要不然只会返回一个地址

复制代码

1
2
3
4
hashList = list(map(hash, [-1.1, -2.6, -2.6, 0, 1, 2]))
print(hashList)
>>>> [-230584300921369601, -1383505805528216578, -1383505805528216578, 0, 1, 2]

后面三种解法时间复杂度都是O(n)

解法1

采用字典的方法，元素对应key，出现的次数对应val
字典API：http://www.runoob.com/python/python-dictionary.html

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def MoreThanHalfNum_Solution(self, numbers):
        # write code here
        if numbers == []:
            return 0
        dictonary = {}
        dictonary = dictonary.fromkeys(numbers, 0)
        for num in numbers:
            dictonary[num] += 1
        for key in dictonary.keys():
            if dictonary[key] * 2 > len(numbers):
                return key
        return 0

运行时间：29ms

占用内存：5736k

解法2

在上一篇博客中，知道了如何找出数组中第k大个数字。地址：找出数组中任意第k大的数字
如果一个数字的个数超过半数，那么第N/2大的数字一定是这个数字，因此用这个方法找出第N/2大的数字，然后判断这个数字的出现次数是不是满足大于长度的二分之一。（N为数组的长度）

复制代码

class Solution:
    def partitionOfK(self, numbers, start, end, k):
        if k < 0 or numbers == [] or start < 0 or end >= len(numbers) or k > end:
            return None
        low = start
        high = end
        key = numbers[start]
        while low < high:
            while low < high and numbers[high] >= key:
                high -= 1
            numbers[low] = numbers[high]
            while low < high and numbers[low] <= key:
                low += 1
            numbers[high] = numbers[low]
        numbers[low] = key
        if low < k:
            return self.partitionOfK(numbers, start + 1, end, k)
        elif low > k:
            return self.partitionOfK(numbers, start, end - 1, k)
        else:
            return numbers[low]
    def checkMoreThanHalf(self, numbers, num):
        times = 0
        for number in numbers:
            if num == number:
                times += 1
        if times * 2 <= len(numbers):
            return False
        return True
    def MoreThanHalfNum_Solution(self, numbers):
        # write code here
        if numbers == []:
            return 0
        result = self.partitionOfK(numbers, 0, len(numbers) - 1, len(numbers) >> 1)
        if self.checkMoreThanHalf(numbers, result):
            return result
        else:
            return 0

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
38
39
class Solution:
    def partitionOfK(self, numbers, start, end, k):
        if k < 0 or numbers == [] or start < 0 or end >= len(numbers) or k > end:
            return None
        low = start
        high = end
        key = numbers[start]
        while low < high:
            while low < high and numbers[high] >= key:
                high -= 1
            numbers[low] = numbers[high]
            while low < high and numbers[low] <= key:
                low += 1
            numbers[high] = numbers[low]
        numbers[low] = key
        if low < k:
            return self.partitionOfK(numbers, start + 1, end, k)
        elif low > k:
            return self.partitionOfK(numbers, start, end - 1, k)
        else:
            return numbers[low]
    def checkMoreThanHalf(self, numbers, num):
        times = 0
        for number in numbers:
            if num == number:
                times += 1
        if times * 2 <= len(numbers):
            return False
        return True
    def MoreThanHalfNum_Solution(self, numbers):
        # write code here
        if numbers == []:
            return 0
        result = self.partitionOfK(numbers, 0, len(numbers) - 1, len(numbers) >> 1)
        if self.checkMoreThanHalf(numbers, result):
            return result
        else:
            return 0

运行时间：35ms

占用内存：5728k

解法3

数组中如果有一个数字出现的次数超过数组长度的一半，也就是说他出现的次数比其他所有的数字出现的次数的和还要多。因此当我们遍历到下一个数字的时候，如果相同，次数加一，不同次数减一，直到0。如果为0，那么保存下一个数字，并把次数设置为1，找的就是最后设置为1的数字

复制代码

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
class Solution:
    def checkMoreThanHalf(self, numbers, num):
        times = 0
        for number in numbers:
            if num == number:
                times += 1
        if times * 2 <= len(numbers):
            return False
        return True
    def MoreThanHalfNum_Solution(self, numbers):
        # write code here
        if numbers == []:
            return 0
        result = numbers[0]
        times = 1
        for i in range(1, len(numbers)):
            if times == 0:
                result = numbers[i]
                times = 1
            elif numbers[i] == result:
                times += 1
            else:
                times -= 1
        if self.checkMoreThanHalf(numbers, result):
            return result
        else:
            return 0