建站
咨詢
售后
建站咨詢
新聞中心
這里有您想知道的互聯(lián)網(wǎng)營銷解決方案
劍指offer：數(shù)組中重復(fù)的數(shù)字
題目描述：
在一個(gè)長度為n的數(shù)組里的所有數(shù)字都在0到n-1的范圍內(nèi)。 數(shù)組中某些數(shù)字是重復(fù)的，但不知道有幾個(gè)數(shù)字是重復(fù)的。也不知道每個(gè)數(shù)字重復(fù)幾次。請(qǐng)找出數(shù)組中任意一個(gè)重復(fù)的數(shù)字。 例如，如果輸入長度為7的數(shù)組{2,3,1,0,2,5,3}，那么對(duì)應(yīng)的輸出是第一個(gè)重復(fù)的數(shù)字2。
公司主營業(yè)務(wù)：網(wǎng)站制作、成都網(wǎng)站制作、移動(dòng)網(wǎng)站開發(fā)等業(yè)務(wù)。幫助企業(yè)客戶真正實(shí)現(xiàn)互聯(lián)網(wǎng)宣傳，提高企業(yè)的競爭能力。成都創(chuàng)新互聯(lián)是一支青春激揚(yáng)、勤奮敬業(yè)、活力青春激揚(yáng)、勤奮敬業(yè)、活力澎湃、和諧高效的團(tuán)隊(duì)。公司秉承以“開放、自由、嚴(yán)謹(jǐn)、自律”為核心的企業(yè)文化，感謝他們對(duì)我們的高要求，感謝他們從不同領(lǐng)域給我們帶來的挑戰(zhàn)，讓我們激情的團(tuán)隊(duì)有機(jī)會(huì)用頭腦與智慧不斷的給客戶帶來驚喜。成都創(chuàng)新互聯(lián)推出靜海免費(fèi)做網(wǎng)站回饋大家。
# -*- coding: utf-8 -*-
# @Time : 2019-04-15 17:31
# @Author : Jayce Wong
# @ProjectName : job
# @FileName : duplicate_num_in_array.py
# @Blog : https://blog.51cto.com/jayce1111
# @Github : https://github.com/SysuJayce
class Solution:
# 這里要特別注意~找到任意重復(fù)的一個(gè)值并賦值到duplication[0]
# 函數(shù)返回True/False
def duplicate(self, numbers, duplication):
# 完整的做法是先進(jìn)行輸入合法性檢查，然后將每個(gè)數(shù)字放到它應(yīng)該在的下標(biāo)，在每次交換之前先檢查該下標(biāo)是否已保存了正確的數(shù)字，
# 如果是則該數(shù)字是一個(gè)重復(fù)數(shù)字
# 時(shí)間復(fù)雜度O(n)，空間復(fù)雜度O(1)。由于每個(gè)數(shù)字最多交換兩次就可以放到正確的位置(第一次被從不正確的位置換到另一個(gè)不正確的位置，
# 然后第二次就會(huì)專門為它找到屬于它的位置，因此最多是兩次)，也就是最多比較2n次，即時(shí)間復(fù)雜度是O(n)
if not numbers:
return False
if max(numbers) >= len(numbers) or min(numbers) < 0:
return False
for i in range(len(numbers)):
while numbers[i] != i:
if numbers[numbers[i]] == numbers[i]:
duplication[0] = numbers[i]
return True
else:
# 注意這樣交換會(huì)出現(xiàn)問題，需要先保存一個(gè)中間結(jié)果，不能直接交換，
# 否則當(dāng)處理numbers[numbers[i]]的時(shí)候會(huì)找不到正確的下標(biāo)
# numbers[i], numbers[numbers[i]] = numbers[numbers[i]], numbers[i]
temp = numbers[i]
numbers[i] = numbers[numbers[i]]
numbers[temp] = temp
return False
def duplicate2(self, numbers, duplication):
# duplicate1()需要對(duì)輸入數(shù)組進(jìn)行修改，假如要求不修改輸入數(shù)組，那么可以借鑒二分查找的
# 思想，逐步縮小重復(fù)數(shù)字所在的區(qū)間。
# 但是這種方法不能確保找到所有重復(fù)的數(shù)字，
# 如果counter(left, right) == right - left + 1，不能排除[left, right]有重復(fù)
# 數(shù)字的情況，例如[2, 3, 5, 4, 3, 2, 6, 7]中，counter(1, 2) == 2，但是2其實(shí)是
# 重復(fù)數(shù)字
# 由于是借鑒了二分查找的思想，因此while需要循環(huán)logn次，counter需要n次運(yùn)算
# 故時(shí)間復(fù)雜度O(nlogn), 空間復(fù)雜度O(1)
def counter(start, end): # 統(tǒng)計(jì)numbers中處于[start, end]之間的數(shù)字個(gè)數(shù)
count = 0
for num in numbers:
if start <= num <= end:
count += 1
return count
if not numbers: # 輸入合法性判斷
return False
left, right = 0, len(numbers) - 1 # 初始區(qū)間為[0, n-1]
while left <= right:
mid = (left + right) >> 1
cnt = counter(left, mid)
# 需要注意這里的循環(huán)出口，如果不在循環(huán)內(nèi)判斷l(xiāng)eft==right的情況的話就需要在循環(huán)外面
# 再判斷一次counter(left, left) == 1
if left == right:
if cnt > 1:
duplication[0] = left
return True
break
if cnt > mid - left + 1:
# 由于是判斷了 [left, mid]是否存在重復(fù)，并不能排除mid就是重復(fù)的數(shù)字，
# 因此right不能更新為mid - 1
right = mid
else:
left = mid + 1
return False
def duplicate3(self, numbers, duplication):
# 由于數(shù)組中的數(shù)字范圍已定，可以通過申請(qǐng)一個(gè)容量為數(shù)字范圍的數(shù)組然后建立哈希表進(jìn)行去重
# 時(shí)間復(fù)雜度O(n), 空間復(fù)雜度O(n)
arr = [-1] * len(numbers)
for num in numbers:
if arr[num] == -1:
arr[num] = num
else:
duplication[0] = num
return True
return False
本文名稱：劍指offer：數(shù)組中重復(fù)的數(shù)字
本文鏈接：http://www.ef60e0e.cn/article/pdhcsi.html
