数组中重复的数字——jzoffer

栈是一个与递归紧密相关的数据结构（深度优先遍历），同样队列也与广度优先遍历算法紧密相关。
数组中的内存是连续的，于是可以根据下标在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