剑指offer系列24---数组中重复的数字

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

书上方法：

 1 package com.exe6.offer;
 2 /**
 3  * 【24】
 4  * 【题目】在一个长度为n的数组里的所有数字都在0到n-1的范围内。
 5  *  数组中某些数字是重复的，但不知道有几个数字是重复的。
 6  *  也不知道每个数字重复几次。
 7  * 请找出数组中任意一个重复的数字。 
 8  * 例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是重复的数字2或者3。
 9  * @author WGS
10  *
11  */
12 public class DuplicationNums {
13 
14     @SuppressWarnings("unused")
15     public  boolean DuplicationNums(int[] nums){
16         if(nums==null ||nums.length <=0) return false;
17         int len=nums.length;
18         for(int i=0;i<len;i++){
19             if(nums[i]>=len){
20                 System.out.println("输入的数不符合要求！");
21                 return false;
22             }
23         }
24         
25         for(int i=0;i<len;i++){
26             while(nums[i]!=i){
27                 if(nums[i]==nums[nums[i]]){
28                     
29                     return true;
30                 }else{
31                     int temp=nums[i];//2
32                     nums[i]=nums[nums[i]];//1
33                     nums[temp]=temp;
34                 }
35             }
36         }
37         return false;
38     }
39     public static void main(String[] args) {
40         int numbers[]=new int[]{2,3,1,0,2,5,3};
41         DuplicationNums d=new DuplicationNums();
42         boolean b=d.DuplicationNums(numbers);
43         System.out.println(b);
44     }
45 
46 }

博主代码，可以显示指定数字重复的次数：

 1 package com.exe6.offer;
 2 
 3 import java.util.HashMap;
 4 import java.util.Map;
 5 
 6 /**
 7  * 【24】
 8  * 【题目】在一个长度为n的数组里的所有数字都在0到n-1的范围内。
 9  *  数组中某些数字是重复的，但不知道有几个数字是重复的。
10  *  也不知道每个数字重复几次。
11  * 请找出数组中任意一个重复的数字。 
12  * 例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是重复的数字2或者3。
13  * @author WGS
14  *
15  */
16 public class DuplicationNums2 {
17 
18 
19     public  boolean DuplicationNums2(int[] nums,int [] duplication){
20         if(nums==null ||nums.length <=1) return false;
21         int len=nums.length;
22         
23         
24         for(int i=0;i<len;i++){
25             if(nums[i]>=len){
26                 System.out.println("输入的数不符合要求！");
27                 return false;
28             }
29         }
30         Map<Integer,Integer> counter=new HashMap<>();
31         for(int i=0;i<len;i++){
32             while(nums[i]!=i){
33                 if(counter.containsKey(nums[i])){
34                     duplication[0]=nums[i];
35                     return true;
36                 }else{
37                     counter.put(nums[i], new Integer(1));
38                 }
39             }
40         }
41         return false;
42     }
43     
44     public static void main(String[] args) {
45         int numbers[]=new int[]{2,3,1,0,2,5,3};
46         DuplicationNums2 d=new DuplicationNums2();
47         boolean b=d.DuplicationNums2(numbers,new int[1]);
48         System.out.println(b);
49     }
50 
51 }

还有更好的方法：

 1 import java.util.Set;
 2 import java.util.HashSet;
 3 public class Solution {
 4     // Parameters:
 5     //    numbers:     an array of integers
 6     //    length:      the length of array numbers
 7     //    duplication: (Output) the duplicated number in the array number,length of duplication array is 1,so using duplication[0] = ? in implementation;
 8     //                  Here duplication like pointor in C/C++, duplication[0] equal *duplication in C/C++
 9     //    这里要特别注意~返回任意重复的一个，赋值duplication[0]
10     // Return value:       true if the input is valid, and there are some duplications in the array number
11     //                     otherwise false
12     public boolean duplicate(int numbers[],int length,int [] duplication) {
13         if(numbers==null ||length<2 ){
14             return false;
15         }
16        Set<Integer> set=new HashSet<>();
17         for(int i=0;i<length;i++){
18             if(!set.add(numbers[i])){
19                 duplication[0]=numbers[i];
20                 return true;
21             }else{
22                 set.add(numbers[i]);
23             }
24         }
25         return false;
26     }
27 }