一、题目
————————————————
在一个长度为n+1的数组里的所有数字都在1到n的范围内,所以数组中至少有一个数字是重复的。请找出数组中任意一个重复的数字,但不能修改输入的数组。例如,如果输入长度为8的数组{2, 3, 5, 4, 3, 2, 6, 7},那么对应的输出是重复的数字2或者3。
————————————————
二、思路
————————————————
方法一:数组长度为n+1,而数字只从1到n,说明必定有重复数字。可以由二分查找法拓展:把1n的数字从中间数字m分成两部分,若前一半1m的数字数目超过m个,说明重复数字在前一半区间,否则,在后半区间m+1~n。每次在区间中都一分为二,知道找到重复数字。
更简单的思路:把该数组看作一个链表,下标代表当前结点,值代表next指针,具体参考Find the Duplicate Number,时间复杂度仅为O(n)
————————————————
三、解决问题
————————————————
测试用例
1.数组中带一个或多个重复数字
2.数组中不包含重复的数字
3.无效输入测试用例(空数组,数组数字越界等)
————————————————
package swordoffer; /** * @author LQ * @version 1.0 * @date 2020-03-13 10:09 */ import java.util.HashMap; import java.util.Objects; /** * 题目:在一个长度为n+1的数组里的所有数字都在1到n的范围内,所以数组中至 * 少有一个数字是重复的。请找出数组中任意一个重复的数字,但不能修改输入的 * 数组。例如,如果输入长度为8的数组{2, 3, 5, 4, 3, 2, 6, 7},那么对应的 * 输出是重复的数字2或者3。 */ public class Solution06 { public static void main(String[] args) { System.out.println("=============================="); Solution06 sword = new Solution06(); sword.test1(); System.out.println("=============================="); sword.test2(); System.out.println("=============================="); sword.test3(); System.out.println("=============================="); } /** * 方法二:(类似二分法) * 时间复杂度:O(nlogn) (while循环为O(logn),coutRange()函数为O(n)) * 空间复杂度:O(1) * 可以由二分查找法拓展:把1~n的数字从中间数字m分成两部分 * 若前一半1~m的数字数目超过m个,说明重复数字在前一半区间 * 否则,在后半区间m+1~n。 * 每次在区间中都一分为二,知道找到重复数字。 * @param array * @return */ public int getDuplicate01(int[] array) { if(null == array || array.length <= 0){ System.out.println("数组输入无效!"); return -1; } //保证数组长度为n+1,而数字只从1到n,说明必定有重复数字 for(int arr : array){ if(arr < 1 || arr > array.length - 1){ System.out.println("数字大小超出范围!"); return -1; } } int low = 1; int high = array.length - 1;// high即为题目的n int mid,count; while(low <= high){ //把1~n的数字从中间数字m分成两部分, mid = ((high - low) >> 2) + low; count = countRange(array,low,mid); if(low == high){ if(count > 1){ return low; }else{ break;// 必有重复,应该不会出现这种情况吧? } } if(count > mid - low + 1){ high = mid;//若前一半1~m的数字数目超过m个,说明重复数字在前一半区间 }else{ low = mid + 1;//否则,在后半区间m+1~n。 } } return -1; } /** * 方法二:构建一个哈希表,遍历数组所有数字 * 判断哈希表中是否存在这个数字: * 如果没有,则添加进哈希表。如果已经存在,则输出该值。 * @param array * @return */ public int getDuplicate02(int[] array) { if(null == array || array.length <= 0){ System.out.println("数组输入无效!"); return -1; } //保证数组长度为n+1,而数字只从1到n,说明必定有重复数字 for(int arr : array){ if(arr < 1 || arr > array.length - 1){ System.out.println("数字大小超出范围!"); return -1; } } //新建一个hashmap HashMap<Integer, Integer> hashMap = new HashMap<>(); //遍历数组中的元素 for (int i = 0; i < array.length; i++) { if(! hashMap.containsKey(array[i])){ //如果hash表中没有该数字,添加并以其本身作为关联键 hashMap.put(array[i],array[i]); }else{ //如果存在该数字了,说明出现重复数字,则返回该数字 return array[i]; } } return -1; } /** * 返回数组元素在[low,high]范围中出现个数 */ public int countRange(int[] array, int low, int high) { if(null == array){ return 0; } int count = 0; for(int arr : array){ if(arr >= low && arr <= high){ count++; } } return count; } // ==================================测试代码================================== /** *数组为null */ public void test1() { System.out.println("test1:"); int[] a = null; System.out.println("方法一:"); int dup = getDuplicate01(a); if (dup >= 0){ System.out.println("重复数字为:" + dup); } dup = 0; System.out.println("方法二:"); dup = getDuplicate02(a); if (dup >= 0){ System.out.println("重复数字为:" + dup); } } /** *数组数字越界 */ public void test2() { System.out.println("test2:"); int[] a = { 1, 2, 3, 4 }; int dup = getDuplicate01(a); if (dup >= 0){ System.out.println("重复数字为:" + dup); } dup = 0; System.out.println("方法二:"); dup = getDuplicate02(a); if (dup >= 0){ System.out.println("重复数字为:" + dup); } } /** *数组带重复数字 */ public void test3() { System.out.println("test3:"); int[] a = { 1, 2, 3, 2, 4 }; int dup = getDuplicate01(a); if (dup >= 0){ System.out.println("重复数字为:" + dup); } dup = 0; System.out.println("方法二:"); dup = getDuplicate02(a); if (dup >= 0){ System.out.println("重复数字为:" + dup); } } }
————————————————
努力也是需要学习的,别再让你的努力,只感动了自己!愿你的每一次努力,都能为自己和别人创造价值。