面試3題：

題：數(shù)組中重復(fù)的數(shù)字

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

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

解題代碼：

# -*- coding:utf-8 -*- class Solution:# 這里要特別注意~找到任意重復(fù)的一個值并賦值到duplication[0]# 函數(shù)返回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

?

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

解題代碼：

# -*- coding:utf-8 -*- class Solution:# 這里要特別注意~找到任意重復(fù)的一個值并賦值到duplication[0]# 函數(shù)返回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

?

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

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

# -*- coding:utf-8 -*- class Solution:# 這里要特別注意~找到任意重復(fù)的一個值并賦值到duplication[0]# 函數(shù)返回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

?

?

拓展：不修改數(shù)組找出重復(fù)的數(shù)字。

''' 拓展：不修改數(shù)組找出重復(fù)的數(shù)字。 在一個長度為n+1的數(shù)組里的所有數(shù)字都在1~n的范圍內(nèi)，所以數(shù)組中至少有一個數(shù)字是重復(fù)的。請找出數(shù)組中任意一個重復(fù)的數(shù)字， 但不能修改輸入的數(shù)組，例如輸入長度為8的數(shù)組[2,3,5,4,3,2,6,7]，那么對應(yīng)的輸出是重復(fù)的數(shù)字為2或3。 '''# 方法一：利用哈希表，時間復(fù)雜度O(n)，空間復(fù)雜度O(n) # 方法二：二分查找的變形，如下，時間復(fù)雜度O(nlogn)，空間復(fù)雜度為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):'''計算數(shù)組中的元素大于等于start，小于等于end的元素的個數(shù)'''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]))

?

轉(zhuǎn)載于:https://www.cnblogs.com/yanmk/p/9232144.html

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

總結(jié)

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

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。