数组中重复数-剑指offer-Java

系统管理员 2021-12-03 22:39 222阅读 0赞

### 题目描述 ###

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

### 解题思路： ###

第一个重复的数字即可；  
采用list.contains进行判断，如果存在，证明就是重复的，直接进行赋值，然后进行返回。

> 1.  package pratice718;
> 2.  import java.util.ArrayList;
> 3.  //题目描述
> 4.  //在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，
> 5.  //但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。
> 6.  //例如，如果输入长度为7的数组\{2,3,1,0,2,5,3\}，那么对应的输出是第一个重复的数字2。
> 7.  //解题思路：
> 8.  //第一个重复的数字即可；
> 9.  //采用list.contains进行判断，如果存在，证明就是重复的，直接进行赋值，然后进行返回。
> 10. public class repateNum\_onerept \{
> 11. // Parameters:
> 12. //    numbers:     an array of integers
> 13. //    length:      the length of array numbers
> 14. //    duplication: (Output) the duplicated number in the array number,length of duplication array is 1,so using duplication\[0\] = ? in implementation;
> 15. //                  Here duplication like pointor in C/C++, duplication\[0\] equal \*duplication in C/C++
> 16. //    这里要特别注意~返回任意重复的一个，赋值duplication\[0\]
> 17. // Return value:       true if the input is valid, and there are some duplications in the array number
> 18. //                     otherwise false
> 19.     public static boolean duplicate(int numbers\[\],int length,int \[\] duplication) \{
> 20.         ArrayList<String> list = new ArrayList<String>();
> 21.         if(numbers==null || numbers.length==0)
> 22.             return false;
> 23.         list.add(numbers\[0\]+"");
> 24.         for(int i=1;i<numbers.length;i++)
> 25.         \{
> 26.             if(list.contains(numbers\[i\]+""))\{
> 27.                 list.remove(numbers\[i\]+"");
> 28.                 duplication\[0\] = numbers\[i\];
> 29.                 return true;
> 30.             \}else\{
> 31.                 list.add(numbers\[i\]+"");
> 32.             \}
> 33.         \}
> 34.         for(int i=0;i<list.size();i++)
> 35.         \{
> 36.             System.out.print(list.get(i)+" ");
> 37.         \}
> 38.         return false;
> 39.     \}
> 40.     public static void main(String\[\] args) \{
> 41.         int array\[\] = \{2,1,3,1,4\};
> 42.         int duplication\[\] =new int\[array.length\];
> 43.         int length = array.length;
> 44.         boolean r = duplicate(array,length,duplication);
> 45.         System.out.println(" "+r+" "+duplication\[0\]);
> 46.     \}
> 47. \}

**扫码关注一起随时随地学习！！！就在洋葱攻城狮，更多精彩，等你来！！**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljeTA3MDY_size_16_color_FFFFFF_t_70][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljeTA3MDY_size_16_color_FFFFFF_t_70]: /images/20211203/f75b93e3a39a41368b9283b42a10a7d9.png