《剑指offer-第二版》-面试题03-数组中重复的数字-01-找出数组中重复的数字(Java)
点击查看: 《剑指offer-第2版》 全部面试题 详解目录(Java版）
题目一： 找出数组中重复的数字
题目描述： 在一个长度为n的数组里的所有数字都在0~n-1的范围内。数组中某些数字是重复的。但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。例如，如果输入长度为7的数组{2,3,1,0,2,5,3},那么对应的输出是重复的数字2或3。
- 思路一： 先排序，在比较。思路简单，时间复杂度为
O(nlogn) - 思路二： 利用哈希表解决，每次向哈希表中存放数据 并比较是否存在, 时间复杂度为
O(n),空间复杂度为O(n) - 思路三: 手动重排，将数组元素放在和其大小对应的下标处。 若该元素现在和数组下标相同 则扫描下一个元素，若不相同
(且对应目标下标处的元素和该元素相同，则发现重复元素，若不同则交换两数位置)时间复杂度为O(n)
思路三的代码实现：
代码中尽管有一个双循环，但每个数字最多只要减缓两次就能找到属于它自己的位置
因此总的时间复杂度为 O(n) , 空间复杂度为 O(1)
package ch02;/** * @author Ren */public class T03_1_找出数组中重复的数字 { public static void main(String[] args) { // 定义一个数组 int [] arr = {2,3,1,0,2,5,3}; // 调用判断方法 duplicate(arr,arr.length); } /** * 代码中尽管有一个双循环，但每个数字最多只要减缓两次就能找到属于它自己的位置 * 因此总的时间复杂度为 O(n) , 空间复杂度为 O(1) * @param arr * @param length * @return */ public static boolean duplicate(int arr[], int length){ //先判断数组是否为空、 if(arr==null || length<=0){ return false; } //遍历数组,如果存在元素 小于0 或 大于数组索引 的情况则不符合题意 for (int i = 0; i < length; i ) { if(arr[i] <0 || arr[i]>=length) { return false; } } //其他情况 即：符合题意的情况 for (int i = 0; i < length; i ) { while (arr[i] != i){ // 如果当前元素 不等于当前索引，并且： 目标索引等于目标索引上的元素，则发现相等元素 if(arr[i]==arr[arr[i]]){ System.out.println(arr[i]); return true; } //当前元素 不等于当前索引，并且： 目标索引不等于目标索引上的元素 int temp = arr[i]; arr[i] = arr[arr[i]]; arr[temp]=temp; } } return false; }} 赞 (0)