面試3題：

題：數組中重復的數字

題目：在一個長度為n的數組里的所有數字都在0到n-1的范圍內。 數組中某些數字是重復的，但不知道有幾個數字是重復的。也不知道每個數字重復幾次。請找出數組中任意一個重復的數字。 例如，如果輸入長度為7的數組{2,3,1,0,2,5,3}，那么對應的輸出是第一個重復的數字2。

解題思路一：先把輸入數組排序，然后從排序后的數組中從前往后找。

解題代碼：

# -*- coding:utf-8 -*- class Solution:# 這里要特別注意~找到任意重復的一個值并賦值到duplication[0]# 函數返回True/Falsedef duplicate(self, numbers, duplication):# write code hereif numbers==None or len(numbers)<=1:return Falsefor i in range(len(numbers)):if numbers[i]<0 or numbers[i]>len(numbers)-1:return Falsenumbers.sort()for i in range(len(numbers)-1):if numbers[i]==numbers[i+1]:duplication[0]=numbers[i]return Truereturn False

?

解題思路二：使用輔助空間:哈希表。時間復雜度為O(n)，空間復雜度為O(n)

解題代碼：

# -*- coding:utf-8 -*- class Solution:# 這里要特別注意~找到任意重復的一個值并賦值到duplication[0]# 函數返回True/Falsedef duplicate(self, numbers, duplication):# write code hereif numbers==None or len(numbers)<=1:return FalseusedDic=set() #集合for i in range(len(numbers)):if numbers[i]<0 or numbers[i]>len(numbers)-1:return Falseif numbers[i] not in usedDic:usedDic.add(numbers[i])else:duplication[0]=numbers[i]return Truereturn False

?

解題思路三：重排數組：從頭到尾掃描數組的每個數字，當掃描到下標為i的數字時，首先比較這個數字（假設為m）是否等于i,如果是，接著掃描下一個數字；如果不是，那么再將它和下標為m的數字對比，如果兩者不相等，就把它和第m個數字交換，把m放到屬于它的位置，如果兩者相等，那么就找到了一個重復的數字。重復這個過程，知道發現一個重復的數字。

解題代碼：(根據代碼分析復雜度：所有操作都在輸入數組上進行，不需要額外分配空間，因此空間復雜度為O(1);盡管代碼中有一個兩重循環，但是每個數字最多只要交換兩次就能找到它自己的位置，因為總的時間復雜度為O(n))

# -*- coding:utf-8 -*- class Solution:# 這里要特別注意~找到任意重復的一個值并賦值到duplication[0]# 函數返回True/Falsedef duplicate(self, numbers, duplication):# write code hereif numbers==None or len(numbers)<=1:return Falsefor i in range(len(numbers)):if numbers[i]<0 or numbers[i]>len(numbers)-1:return Falsefor i in range(len(numbers)):while (numbers[i]!=i):if numbers[i]==numbers[numbers[i]]:duplication[0]=numbers[i]return Trueelse:temp=numbers[i]numbers[i]=numbers[temp]numbers[temp]=tempreturn False

?

?

拓展：不修改數組找出重復的數字。

''' 拓展：不修改數組找出重復的數字。 在一個長度為n+1的數組里的所有數字都在1~n的范圍內，所以數組中至少有一個數字是重復的。請找出數組中任意一個重復的數字， 但不能修改輸入的數組，例如輸入長度為8的數組[2,3,5,4,3,2,6,7]，那么對應的輸出是重復的數字為2或3。 '''# 方法一：利用哈希表，時間復雜度O(n)，空間復雜度O(n) # 方法二：二分查找的變形，如下，時間復雜度O(nlogn)，空間復雜度為O(1)class Solution:def duplicate(self, numbers):# write code hereif not numbers or len(numbers)<=0:return -1start=1end=len(numbers)-1while start<=end:middle=(end-start)//2+startcount=self.countRange(numbers,len(numbers),start,middle)if end==start:if count>1:return startelse:breakif count>middle-start+1:end=middleelse:start=middle+1return -1def countRange(self,numbers,length,start,end):'''計算數組中的元素大于等于start，小于等于end的元素的個數'''if not numbers:return 0count=0for i in range(length):if numbers[i]>=start and numbers[i]<=end:count+=1return countif __name__=="__main__":print(Solution().duplicate([2,3,5,4,3,2,6,7]))

?

轉載于:https://www.cnblogs.com/yanmk/p/9232144.html

《新程序員》：云原生和全面數字化實踐50位技術專家共同創作，文字、視頻、音頻交互閱讀

總結

以上是生活随笔為你收集整理的剑指offer 面试3题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。