栈是一个与递归紧密相关的数据结构（深度优先遍历），同样队列也与广度优先遍历算法紧密相关。
数组中的内存是连续的，于是可以根据下标在O(1)时间读/写任何元素，可以用数组实现简单的哈希表（字典），既可以将下标设置为key，也可以将元素值设置为key（如果元素不重复的话）；
为了解决数组空间效率不高的问题，人们设计实现了动态数组，为了避免浪费，我们先为数组开辟小的空间，然后往数组中添加数据，当数组的数目超过一个阈值（跟当前数组长度有关），我们再重新分配更大的空间（C++的STL中的vector每次扩容，新的容量是前一次的两倍）。但是每一次扩充数组容量时都有大量的额外操作，对时间性能有负面影响，因此使用动态数组时，尽量减少改变数组容量大小的操作。
问题：长度为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)
# 节省空间的方法，实现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
网友评论