题目描述

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

 

class Solution {public:    // Parameters:    //        numbers:     an array of integers    //        length:      the length of array numbers    //        duplication: (Output) the duplicated number in the array number    // Return value:       true if the input is valid, and there are some duplications in the array number    //                     otherwise false    bool duplicate(int numbers[], int length, int* duplication) {        if(!numbers || length<=0)    return false;        for(int i=0;i
       
        length-1)                return false;        }                int hashTable[length];        for(int i=0;i
       

您的代码已保存

答案错误:您提交的程序没有通过所有的测试用例

case通过率为33.33%

测试用例:

[2,4,2,1,4]

对应输出应该为:

"true,2"

你的输出为:

"true,4"

 

class Solution {public:bool duplicate(int array[], int length, int *duplication) {    if (length==0 ) return false;    // 判断数组是否合法（每个数都在0~n-1之间）    for ( int i=0; i
       
        length-1 ) {            return false;        }    }    // key step    int *hash=new int[length];    for( int i=0; i
        
         1 ) {            *duplication =array[i];            return true;        }    }    return false;    }};
        
       

 

 

class Solution{    public:        // Parameters:        //        numbers:     an array of integers        //        length:      the length of array numbers        //        duplication: (Output) the duplicated number in the array number        // Return value:       true if the input is valid, and there are some duplications in the array number        //                     otherwise false        bool duplicate(int num[], int len, int* duplication)        {            if(len==0)                return false;            for(int i = 0; i

 

 

 

 

下面是Java的实现方式。

 

思路1：哈希法

1. 由于所有元素值是有范围的，因此可以用一个长度为n的数组，下标表示序列中的每一个值，下标对应的值表示该下标出现的次数。
2. 只需扫描一次原序列，就统计出所有元素出现的次数；
3. 再扫描一次哈希数组，找到一个出现次数大于1的值即可。

　　这种方法时间复杂度和空间复杂度都为O(n)。

 

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 array[],int length,int [] duplication) {if ( array==null ) return false;    // 判断数组是否合法（每个数都在0~n-1之间）    for ( int i=0; i
       
        length-1 ) {            return false;        }    }    // key step    int[] hash = new int[length];    for( int i=0; i
        
         1 ) {            duplication[0] = i;            return true;        }    }    return false;
        
       

 

思路2：高级此大法利用了哈希的特性，但不需要额外的存储空间。 因此时间复杂度为O(n)，不需要额外空间！把当前序列当成是一个下标和下标对应值是相同的数组；遍历数组，判断当前位的值和下标是否相等： 2.1. 若相等，则遍历下一位； 2.2. 若不等，则将当前位置i上的元素和a[i]位置上的元素比较：若它们相等，则成功！若不等，则将它们两交换。换完之后a[i]位置上的值和它的下标是对应的，但i位置上的元素和下标并不一定对应；重复2.2的操作，直到当前位置i的值也为i，将i向后移一位，再重复2.public boolean duplicate(int array[],int length,int [] duplication) {    if ( array==null ) return false;    // 判断数组是否合法（每个数都在0~n-1之间）    for ( int i=0; i
       
        length-1 ) {            return false;        }    }    // key step    for( int i=0; i