20190912——剑指offer 面试题3 题目1找出数组中重复的数字

题目一：找出数组中重复的数字，在一个长度为n的数组里所有数字都在0~n-1的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。例如，如果输入长度为7的数组{2，3，1，0，2，5，3} ，那么对应的输出是重复的数字2和3

书中的给出的思路与分析一共为三种。
第一种，解决这个问题的一个简单的方法是先把输入的数组排序。从排序的数组中找到重复的数字是一个很容易的事情，只需要从头到尾扫描排序后的数组就可以了。排序一个长度为n的数组需要nlogn的时间。

class Solution(object):
    def duplicate(self,number,duplication):
        """
        :param number: 输入的数组
        :param duplication: 输出重复数字的数组
        :return:
        """
        # 首先判断数组是否为空 长度是否为0
        if number == [] or len(number) < 0 :
            return False
        #在判断数组中的每个元素值不能小于0，不能大于数组长度-1
        for i in number:
            if i < 0 or i>len(number):
                return  False
        #排序数组
        number.sort()
        #数组进行排序过后，寻找重复的数字
        for i in range(len(number)-1):
            if number[i] == number[i+1]:
                if number[i] not in duplication:
                    duplication.append(number[i])
        return duplication

mmz = Solution()
number = [1,2,3,2,1,5,3]
duplication = []
mmz.duplicate(number,duplication)
print(duplication)

如果数组为空，说明有错。

第二种是哈希表的方式解决问题，从头到尾按顺序扫描数组每个数字，每扫描到一个数字的时候，都可以用O（1）的事件来判断哈希表中是否已经包含了该数字，如果哈希表里还没有这个数字，就把它加入哈希表中，如果哈希表已经存在该数字，就找到一个重复的数字，这个算法的时间的复杂度为O（n）但是他是以空间复杂度O（n）的哈希表为代价。

第三种是交换数组，数组中的数字都在0~n-1的范围内，如果这个数组中没有重复的数字，那么当数组排序之后数字i将会出现在下标为i的位置。由于数组中有重复的数字，有些位置可能存在多个数字，同时有些位置可能没有数字。