剑指offer(第二版)leetcode-python3实现（代码+注释）

剑值offer03.数组中的重复数字

在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。 请找出数组中任意一个重复的数字。 示例 1： 输入： [2, 3, 1, 0, 2, 5, 3] 输出：2 或 3

法一：

思路：利用排序算法，对数组进行排序后，其重复数字一定是相领的。所有，我们首先对给定的数组进行排序，然后逐一比较前后两个元素是否相同，相同则返回当前元素值（题目要求输出任意一个重复的数字），并退出。

代码实现：

class Solution:
    def findRepeatNumbe(self,list):
        a = sorted(list) # 排序后,相同的数一定在相邻的位置
        for i in range(len(list) - 1): #最后一次比较是，倒数第二个元素和最后一个元素进行比较，所以整个数组索引的长度-1
            if a[i] == a[i + 1]: #比较相领的元素
                return a[i] #返回首个出现重复的元素

list = [2, 3, 1, 0, 2, 5, 3]
test =Solution()
print(test.findRepeatNumbe(list))

法二：

思路：利用 in 判断列表中是否有重复的元素，若当前元素不在列表中，则将当前元素添加在列表里，若当前元素在列表中则返回当前重复元素。

代码实现：

class Solution:
    def findRepeatNumber(self, nums: int) -> int:
        dic =[] #创建空列表，储存逐一储存nums中的元素
        for num in nums: # 遍历nums中的每一个元素
            if num in dic: # 判断当前元素是否在dic中
                return num # 在则返回当前重复元素
            else:
                dic.append(num) #若当前元素不在dic中，则将当前元素添加在列表中
        return -1

list = [2, 3, 1, 0, 2, 5, 3]
test = Solution()
print(test.findRepeatNumber(list))

法三：
思路：利用numpy中的bincout()方法，该方法会返回一组序列中可能出现元素的重复次数。

代码实现：

import numpy as np
list = [2, 3, 1, 0, 2, 5, 3]
def findRepeatNumbe(list):
    x = np.bincount(list)# x=[1 1 2 2 0 1]对应着0，1，2，3，4，5这些元素在列表中重复出现的次数

# bincount()方法，返回了给定的一组序列，按顺序从最小值（本文中的0）到最大值（本文中的5）在列表中的出现次数

    for i in range(len(list)): # 遍历整个列表
        if x[i]>1:  # 重复出现则代表至少出现2次
            return i  #返回首个出现重复的元素

print(findRepeatNumbe(list))