1 数组中重复数字

题目

在一个长度为n的数组里所有数字都是在0~n-1范围内.数组中某些数字是重复的.但是不知道有几个数字重复了.也不知道每个数字重复了几次.请找出数组中任意一个重复的数字.如果有重复的,返回true.如果没有.返回false

三种思路

• 排序,然后从头到尾扫描,时间复杂度是O(nlogn)
• 哈希表
  从头到尾顺序扫描每个元素,每扫描到一个数字,判断这个哈希表里是否存在.如果没有就加入,如果有就不加入.返回true.时间复杂度是O(n),但是需要额外的存储空间O(n)
• 时间复杂度O(n),空间复杂度是O(1)
  从头开始扫描,如果当前的i位置的元素并不是i.而是j.就把i和j互换位置,如果还不是就一直替换到第i个位置的元素为i位置