package com.exe6.offer;

 /**

  * 【24】

  * 【题目】在一个长度为n的数组里的所有数字都在0到n-1的范围内。

  *  数组中某些数字是重复的，但不知道有几个数字是重复的。

  *  也不知道每个数字重复几次。

  * 请找出数组中任意一个重复的数字。

  * 例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是重复的数字2或者3。

  * @author WGS

  *

  */

 public class DuplicationNums {

     @SuppressWarnings("unused")

     public  boolean DuplicationNums(int[] nums){

         if(nums==null ||nums.length <=0) return false;

         int len=nums.length;

         for(int i=0;i<len;i++){

             if(nums[i]>=len){

                 System.out.println("输入的数不符合要求！");

                 return false;

             }

         }

         for(int i=0;i<len;i++){

             while(nums[i]!=i){

                 if(nums[i]==nums[nums[i]]){

                     return true;

                 }else{

                     int temp=nums[i];//

                     nums[i]=nums[nums[i]];//

                     nums[temp]=temp;

                 }

             }

         }

         return false;

     }

     public static void main(String[] args) {

         int numbers[]=new int[]{2,3,1,0,2,5,3};

         DuplicationNums d=new DuplicationNums();

         boolean b=d.DuplicationNums(numbers);

         System.out.println(b);

     }

 }

 package com.exe6.offer;

 import java.util.HashMap;

 import java.util.Map;

 /**

  * 【24】

  * 【题目】在一个长度为n的数组里的所有数字都在0到n-1的范围内。

  *  数组中某些数字是重复的，但不知道有几个数字是重复的。

  *  也不知道每个数字重复几次。

  * 请找出数组中任意一个重复的数字。

  * 例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是重复的数字2或者3。

  * @author WGS

  *

  */

 public class DuplicationNums2 {

     public  boolean DuplicationNums2(int[] nums,int [] duplication){

         if(nums==null ||nums.length <=1) return false;

         int len=nums.length;

         for(int i=0;i<len;i++){

             if(nums[i]>=len){

                 System.out.println("输入的数不符合要求！");

                 return false;

             }

         }

         Map<Integer,Integer> counter=new HashMap<>();

         for(int i=0;i<len;i++){

             while(nums[i]!=i){

                 if(counter.containsKey(nums[i])){

                     duplication[0]=nums[i];

                     return true;

                 }else{

                     counter.put(nums[i], new Integer(1));

                 }

             }

         }

         return false;

     }

     public static void main(String[] args) {

         int numbers[]=new int[]{2,3,1,0,2,5,3};

         DuplicationNums2 d=new DuplicationNums2();

         boolean b=d.DuplicationNums2(numbers,new int[1]);

         System.out.println(b);

     }

 }

 import java.util.Set;

 import java.util.HashSet;

 public class Solution {

     // Parameters:

     //    numbers:     an array of integers

     //    length:      the length of array numbers

     //    duplication: (Output) the duplicated number in the array number,length of duplication array is 1,so using duplication[0] = ? in implementation;

     //                  Here duplication like pointor in C/C++, duplication[0] equal *duplication in C/C++

     //    这里要特别注意~返回任意重复的一个，赋值duplication[0]

     // Return value:       true if the input is valid, and there are some duplications in the array number

     //                     otherwise false

     public boolean duplicate(int numbers[],int length,int [] duplication) {

         if(numbers==null ||length<2 ){

             return false;

         }

        Set<Integer> set=new HashSet<>();

         for(int i=0;i<length;i++){

             if(!set.add(numbers[i])){

                 duplication[0]=numbers[i];

                 return true;

             }else{

                 set.add(numbers[i]);

             }

         }

         return false;

     }

 }