查找算法

动态规划是算法与数据结构的重难点之一，其包含了「分治思想」、「空间换时间」、「最优解」等多种基石算法思想

数组中重复的数字

在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。

输入：
[2, 3, 1, 0, 2, 5, 3]
输出：2 或 3 
2 <= n <= 100000

def findRepeatNumber( nums):
    """
    :type nums: List[int]
    :rtype: int
    """
    checklist = []
    for i in nums:
        if i not in checklist:
            checklist.append(i)
        else:
            return i


def findRepeatNumber2(nums):
    """
    :type nums: List[int]
    :rtype: int
    """
    checkset = set()
    for i in nums:
        if i not in checkset:
            checkset.add(i)
        else:
            return i

小结：发现python中set速度优于list
循环速度: list最适合做固定长度的遍历，而且有顺序。所以这种循环尽量用list
查询速度: set > list, set查询的key都是hash过的，所以速度最快，list不适合用来做查询
增删速度: set > list, list的append操作尽量少做，因为会涉及重新分配地址的问题，set只需要增长指针链表