在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如，如果输入长度为7的数组{

在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如，如果输入长度为7的数组{

剑指Offer

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

提示

排序思想哈希表题目数组特性

解题思路

排序思想（简单） 利用数组排序算法 排序后很容易找到

哈希表思想 模拟一个哈希表的思想 对数组进行一个哈希表的插入操作 这里由于都是小于n的数字 可以采用对n取余的操作进行哈希 哈希冲突值就是重复的值 空间负责度O(n) 时间复杂度O(n)

数组 0 到n-1特性（牛逼） 题目数组：0到n-1 数组下标：0到n-1 将 数组值 0到n-1对应 数组 的 下标 0到n-1 进行放置！！！ 就是将数组的值依次按下标放置，一旦放置的下标存在一样的值就是找到.

实例：{3,1,4,2,1}

判断3是否处于正确的位置如果不处于正确的位置将3交换到3的位置：{2,1,4,3,1}继续交换 {4,1,2,3,1},{1,1,2,3,4}{1,1,2,3,4}这个时候再执行1的交换的时候发现1已经存在了所以返回1

时间复杂度O(n) 空间复杂度O(1)

代码实现

排序思想

public boolean duplicate(int numbers[],int length,int [] duplication) { if(numbers == null || duplication == null) { return false; } if(numbers.length == 0 || duplication.length == 0){ return false; } if(numbers.length != length){ return false; } //选择排序的思想 for(int i = 0;i < length-1; i++){ for(int j = i+1; j < length; j++) { if(numbers[j] > length -1){ return false; } if(numbers[i] == numbers[j]) { duplication[0] = numbers[i]; return true; } } } return false;}

哈希表思想

public boolean duplicate(int numbers[],int length,int [] duplication) { if(numbers == null || duplication == null) { return false; } if(numbers.length == 0 || duplication.length == 0){ return false; } if(numbers.length != length){ return false; } //空间换时间 int[] hash = new int[length]; for(int i = 0; i < length; i++){ if(numbers[i] >= length){ return false; } int key = numbers[i]%length; if(hash[key] != 0 ){ duplication[0] = hash[key]; return true; } hash[key] = numbers[i]; } return false;}

数组 0 到n-1特性（牛逼）

public boolean duplicate(int numbers[],int length,int [] duplication) { if(numbers == null || duplication == null) { return false; } if(numbers.length == 0 || duplication.length == 0){ return false; } if(numbers.length != length){ return false; } for(int i = 0; i < length; i++){ if(numbers[i] >= length){ return false; } //不处于正确的位置上 while(numbers[i] != i){ //正确的位置上已经有值了 if(numbers[i] == numbers[numbers[i]]){ duplication[0] = numbers[i]; return true; } int swap = numbers[i]; numbers[i] = numbers[swap]; numbers[swap] = swap; } } return false; }

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。