【數組】數組中重複的數字

數組中重複的數字

找出數組中重複的數字。

在一個長度為 n 的數組 nums 裡的所有數字都在 0～n-1 的範圍内。數組中某些數字是重複的，但不知道有幾個數字重複了，也不知道每個數字重複了幾次。請找出數組中任意一個重複的數字。

示例 1：

輸入：

[2, 3, 1, 0, 2, 5, 3]

輸出：2 或 3

限制：

2 <= n <= 100000

方法1：

直接使用count函數，進行統計，遇到出現次數不為1的直接輸出即可。

【錯誤】：超過了限定的時間

python
class Solution(object):
    def findRepeatNumber(self, nums):
        for i in nums:
            if nums.count(i) != 1:    #統計出現的次數，如果不為1，直接輸出，并且傳回
                print(i)                      #循環結束
                return i
        return  '#'
           

方法2

思路：排序方法：

1、先将數組排好序

2、在查找重複數字：先用第一個元素進行對比，如果後邊有和它相等的，直接傳回該元素，沒有的話，用第二個元素和後繼的元素依次比較。

時間複雜度O(nlogn),空間複雜度O(1)

class Solution(object):
 def findRepeatNumber(self, nums):
     nums.sort()        #排序
     p = nums[0]                #将第一個元素賦給p
     for i in range(1, len(nums)):    #對清單從第二個元素開始周遊
         if p == nums[i]:                 #如果P=
             return p
         pre = nums[i]
           

方法3

思路：使用字典。

1、周遊整個數組,當這個數字沒有出現過字典裡有的元素的時候，将其加入進去,如果字典中存在，直接傳回即可

2、時間複雜度O(n),空間複雜度O(n)

class Solution(object):
    def findRepeatNumber(self, nums):
        dic = {}                  #定義空字典
        for i in nums:     #周遊數組
            if i not in dic:      #判斷數組元素是否在字典中，不在的話，就放進字典即可
                dic[i] = 0          #value随便賦，因為是對key進行操作
            else:              #否則，直接傳回重複元素
                return i