棧是一個與遞歸緊密相關的數據結構（深度優(yōu)先遍歷），同樣隊列也與廣度優(yōu)先遍歷算法緊密相關浪读。
數組中的內存是連續(xù)的盟蚣，于是可以根據下標在O(1)時間讀/寫任何元素，可以用數組實現簡單的哈希表（字典）故爵，既可以將下標設置為key，也可以將元素值設置為key（如果元素不重復的話）隅津；
為了解決數組空間效率不高的問題诬垂，人們設計實現了動態(tài)數組，為了避免浪費伦仍，我們先為數組開辟小的空間结窘，然后往數組中添加數據，當數組的數目超過一個閾值（跟當前數組長度有關）充蓝，我們再重新分配更大的空間（C++的STL中的vector每次擴容隧枫，新的容量是前一次的兩倍）。但是每一次擴充數組容量時都有大量的額外操作谓苟，對時間性能有負面影響官脓，因此使用動態(tài)數組時，盡量減少改變數組容量大小的操作涝焙。
問題：長度為n的數組卑笨，數組在0~n-1的范圍內，存在重復數字仑撞，不知道重復次數赤兴，不知道幾個重復數字妖滔，請找出任意一個。
方法一：從排序后的數組中查找桶良，排序的話使用快速排序或者歸并排序座舍，時間復雜度為O(nlogn)
# 我的錯誤答案
def sort_(seq, begin, end):
if len(seq) < 2:
return seq
pivot = get_pivot(seq, begin, end)
left_side = sort_(seq, begin, pivot)
right_side = sort_(seq, pivot+1, end)
return left_side + seq[pivot] + right_side
def get_pivot(seq, begin, end):
pivot = 0
pivot_value = seq[0]
left = 1
right = len(seq) - 1
while left < right:
while seq[left] < pivot_value and left < right:
left += 1
while seq[right] > pivot_value and right > left:
right -= 1
seq[left], seqp[right] = seq[right], seq[left]
seq[left], seq[pivot] = seq[pivot], seqp[left]
# pythonic方式
def sort_(seq):
if len(seq) < 2:
return seq
pivot = 0
pivot_value = seq[0]
left_side = [seq[i] for i in seq[1:] if seq[i] < pivot_value]
right_side = [seq[i] for i in seq[1:] if seq[i] >= pivot_value]
return sort_(left_side) +[pivot_value] + sort_(right_side)
# 節(jié)省空間的方法，實現inplace排序
def sort_(seq, beg, end):
if beg < end:
pivot = get_pivot(seq, begin, end)
sort_(seq, begin, pivot)
sort_(seq, pivot+1, end)
def get_pivot(seq, begin, end):
pivot = begin
pivot_value = seq[begin]
left = begin + 1
right = end
while True:
while seq[left] < pivot_value and left <= right:
left += 1
while seq[right] > pivot_value and left <= right:
right += 1
if left > right:
break
else:
seq[left], seq[right] = seq[right], seq[left]
seq[right], seq[pivot] = seq[pivot], seq[right]
return right
方法二：遍歷數組陨帆，將元素放到哈希表中曲秉，如果哈希表中包含元素，就返回該元素疲牵，時間復雜度為O(n)岸浑，需要一個大小為O(n)的哈希表作為代價
def get_multi(seq):
d = {}
for k, v in enumerate(seq):
if v not in d:
d[v] = k
else:
print (k, v)
break
方法三：時間復雜度為O(n)，空間復雜度為O(1)
def get_multe(seq):
for i in xrange(len(seq)):
if seq[i] < 0 or seq[i] > len(seq) - 1:
raise Exception("nonono")
for index, value in enumerate(seq):
while seq[index] != index:
if seq[value] == value:
return value
else:
seq[index], seq[value] = seq[value], seq[index]
不修改數組找出重復數字
在一個長度為n+1的數組里瑰步，所有數字都在1~n的范圍內矢洲，所以數組至少有一個數字是重復的。請找出任意一個缩焦，但是不能修改輸入的數組读虏。
我的想法：
利用額外的空間，比如上面的通過hash表來查找重復數字袁滥，這樣的話代價是空間復雜度O(1)
答案的想法：
針對1~n范圍內的數盖桥，如果在數組中存在大于n個，代表有重復题翻；
通過二分法做這個判斷揩徊，但是無法找到全部的重復數字，比如1~2范圍內兩個數字嵌赠，數組中有[1, 1]就無法拿出重復數字1
class Solution(object):
def count_(self, seq, length, beg, end):
if beg > end:
raise Exceptino("wrong")
count = 0
for i in range(length):
if seq[i] >= beg and seq[i] <= end:
count += 1
return count
# 我的思路
def get_multi(self, seq, beg, end):
mid = (end - beg) / 2
# mid = (end - beg) >> 1
count_all = self.count_(seq, beg, end)
if end == beg and count_all > 1:
return True
while beg <= end:
count_left = self.count_(seq, beg, mid)
left = mid - beg + 1
count_right = self.count_(seq, mid+1, end)
right = end - mid
if count_ > left or :
# 答案
def get_multi(self, seq, length):
if len(seq) == 0 or length <= 0:
raise Exception("wrong")
beg = 1
end = length - 1
while beg <= end:
mid = (end - beg) >> 1 + beg
count_all = self.count_(seq, length, beg, mid)
if end == beg:
if count_all > 1:
return beg
else:
break
if count_all > mid - beg + 1:
end = mid
else:
beg = mid + 1
return False
