首页 > 试题广场 > 数组中重复的数字
[编程题]数组中重复的数字
在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的,但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如,如果输入长度为7的数组{2,3,1,0,2,5,3},那么对应的输出是第一个重复的数字2。
推荐
不需要额外的数组或者hash table来保存,题目里写了数组里数字的范围保证在0 ~ n-1 之间,所以可以利用现有数组设置标志,当一个数字被访问过后,可以设置对应位上的数 + n,之后再遇到相同的数时,会发现对应位上的数已经大于等于n了,那么直接返回这个数即可。

代码是C:

int find_dup( int numbers[], int length) {

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

        int index = numbers[i];

        if (index >= length) {

            index -= length;

        }   

        if (numbers[index] >= length) {

            return index;

        }   

        numbers[index] = numbers[index] + length;

    }   

    return - 1

}


不需要额外的空间消耗,时间效率是O(n)
编辑于 2015-06-19 16:59:45 回复(74)
//boolean只占一位,所以还是比较省的
	public boolean duplicate(int numbers[], int length, int[] duplication) {
		boolean[] k = new boolean[length];
		for (int i = 0; i < k.length; i++) {
			if (k[numbers[i]] == true) {
				duplication[0] = numbers[i];
				return true;
			}
			k[numbers[i]] = true;
		}
		return false;
	}

发表于 2016-03-26 11:47:55 回复(57)
    bool duplicate(int numbers[], int length, int* duplication) {
        for(int i=0;i!=length;++i){
            int index=numbers[i]%length;
            if(numbers[index]>=length){
                *duplication=index;
                return 1;
            }               
            numbers[index]+=length;   
        }
        return 0;
    }

编辑于 2016-07-11 21:34:06 回复(17)

思路1:哈希法

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

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

public boolean duplicate(int array[],int length,int [] duplication) {
    if ( array==null ) return false;

    // 判断数组是否合法(每个数都在0~n-1之间)
    for ( int i=0; i<length; i++ ) {
        if ( array[i]<0 || array[i]>length-1 ) {
            return false;
        }
    }

    // key step
    int[] hash = new int[length];
    for( int i=0; i<length; i++ ){
        hash[array[i]]++;
    }
    for(int i=0; i<length; i++){
        if ( hash[i]>1 ) {
            duplication[0] = i;
            return true;
        }
    }
    return false;
}

思路2:高级

此大法利用了哈希的特性,但不需要额外的存储空间。 因此时间复杂度为O(n),不需要额外空间!

  1. 把当前序列当成是一个下标和下标对应值是相同的数组;
  2. 遍历数组,判断当前位的值和下标是否相等: 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; i++ ) {
        if ( array[i]<0 || array[i]>length-1 ) {
            return false;
        }
    }

    // key step
    for( int i=0; i<length; i++ ){
        while( i!=array[i] ){
            if ( array[i] == array[array[i]] ) {
                duplication[0] = array[i];
                return true;
            }

            int temp = array[i];
            array[i] = array[array[i]];
            array[array[i]] = temp;
        }
    }

    return false;
}
发表于 2017-03-23 16:27:04 回复(34)
/*
1、判断输入数组有无元素非法
2、从头扫到尾,只要当前元素值与下标不同,就做一次判断,numbers[i]与numbers[numbers[i]],相等就认为找到了
重复元素,返回true,否则就交换两者,继续循环。直到最后还没找到认为没找到重复元素,返回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 numbers[], int length, int* duplication) {
        if(length<=0||numbers==NULL)
            return false;
        //判断每一个元素是否非法
        for(int i=0;i<length;++i)
        {
            if(numbers[i]<=0||numbers[i]>length-1)
                return false;
        }
        for(int i=0;i<length;++i)
        {
            while(numbers[i]!=i)
            {
                if(numbers[i]==numbers[numbers[i]])
                {
                    *duplication = numbers[i];
                    return true;
                }
                //交换numbers[i]和numbers[numbers[i]]
                int temp = numbers[i];
                numbers[i] = numbers[temp];
                numbers[temp] = temp;
            }
        }
        return false;
        
    }
};

发表于 2016-03-26 14:13:21 回复(26)
最简单的方法:我最直接的想法就是构造一个容量为N的辅助数组B,原数组A中每个数对应B中下标,首次命中,B中对应元素+1。如果某次命中时,B中对应的不为0,说明,前边已经有一样数字了,那它就是重复的了。
举例:A{1,2,3,3,4,5},刚开始B是{0,0,0,0,0,0},开始扫描A。
A[0] = 1  {0,1,0,0,0,0}
A[1] = 2 {0,1,1,0,0,0}
A[2] = 3 {0,1,1,1,0,0}
A[3] = 3 {0,1,1,2,0,0},到这一步,就已经找到了重复数字。
A[4] = 4 {0,1,1,2,1,0}
A[5] = 5 {0,1,1,2,1,1}
时间复杂度O(n),空间复杂度O(n),算法优点是简单快速,比用set更轻量更快,不打乱原数组顺序。
如果不能用辅助空间,可以参照剑指。
public class Solution {
    public boolean duplicate(int numbers[],int length,int [] duplication) {
    	int[] assist = new int [length];
        for(int i = 0; i < length; i++){
            if(assist[numbers[i]] == 0){
                assist[numbers[i]] ++;
            }else{
                duplication[0] = numbers[i];
                return true;
            }
        }
        return false;
    }
}

编辑于 2016-08-24 12:12:13 回复(16)
// 别的我不知道,Java版本的这个题目出得跟shit一样。

发表于 2017-07-21 11:03:06 回复(1)
import java.util.*;
public class Solution {    
public boolean duplicate(int numbers[],int length,int [] duplication) {
//方法1:
     if(numbers == null || numbers.length == 0) return false;
        Arrays.sort(numbers);
        int flag = 0;//做标记
        for(int i=0;i<length-1;i++) {
            if(numbers[i] == numbers[i+1]) {
                duplication[0] = numbers[i];
                flag = 1;
                break;
            }
        }
        return flag == 1? true:false;
//方法2:
        HashSet<Integer> hs = new HashSet<>();
        for(int i=0;i<length;i++) {
            if(!hs.add(numbers[i])) {
                duplication[0]=numbers[i];
                return true;
            }
        }
        return false;
    }
}

编辑于 2016-07-18 20:57:03 回复(9)
張头像
/*
 *   对BoTinker的完善
 */
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) {      
        for(int i=0;i<length;i++){            
            int j=numbers[i]%length;
            numbers[j]+=length;
            if(numbers[j]>=(2*length)){
                *duplication = numbers[j]%length;
                return true;
            }                                  
        }
        return false;       
    }
};

发表于 2015-09-09 15:01:03 回复(8)
//时间O(n), 空间O(1)
public class Solution {
        public boolean duplicate(int numbers[],int length,int [] duplication) {
        if(numbers == null || length <= 0) {
            return false;
        }
        
        for(int i = 0; i < length; i++) {
            while(numbers[i] != i) {
                if(numbers[i] == numbers[numbers[i]]) {
                    duplication[0] = numbers[i];
                    return true;
                }
                int temp = numbers[i];
                numbers[i] = numbers[temp];
                numbers[temp] = temp;
            }
        }
        
        return false;
    }
} 
/* 一开始交换写错了写成了这:
int temp = numbers[i];
numbers[i] = numbers[numbers[i]];
numbers[numbers[i]] = temp;
于是就错了...

这就是剑指offer的思路。
*/

编辑于 2018-05-05 00:39:31 回复(9)
代码可以不用贴了
不通过
您的代码已保存
答案错误:您提交的程序没有通过所有的测试用例
case通过率为0.00%

测试用例:
[2,1,3,1,4]

对应输出应该为:

"true,1"

你的输出为:

true,1
# -*- coding:utf-8 -*-
class Solution:
    # 这里要特别注意~找到任意重复的一个值并赋值到duplication[0]
    # 函数返回True/False
    def duplicate(self, numbers, duplication):
        # write code here
        lst = []
        for x in numbers:
            if x in lst:
                duplication[0] = x
                return True
            else:
                lst.append(x)
        return False

编辑于 2018-01-07 11:51:38 回复(15)
你们有没有遇到这个问题
测试用例:
[2,1,3,1,4]

对应输出应该为:

"true,[1]"

你的输出为:

"true,1"
发表于 2017-06-12 14:32:24 回复(14)
class Solution {
public:
    bool duplicate(int numbers[], int length, int* duplication) {
        if(length<=1) return false;
        vector<int> numbers_index(length,0);
        for(int i=0;i<length;i++){
            numbers_index[numbers[i]]++;
            if(numbers_index[numbers[i]]>1){
                *duplication=numbers[i]; 
                return true;
            } 
        }
        return false;
    }
};

发表于 2015-08-22 11:17:10 回复(1)
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) {
    	StringBuffer sb = new StringBuffer();	
        for(int i = 0; i < length; i++){
                sb.append(numbers[i] + "");
            }
        for(int j = 0; j < length; j++){
            if(sb.indexOf(numbers[j]+"") != sb.lastIndexOf(numbers[j]+"")){
                duplication[0] = numbers[j];
                return true;
            }
        }
        return false;
    }
}

发表于 2015-10-13 19:23:49 回复(5)
//duplication只有一个值,居然还用指针,醉了

   bool duplicate(int numbers[], int length, int* duplication) {
        if(length<=0) return false;
        int index=0;
        map<int,int>m;
        for(int i=0;i<length;++i)
        {
             ++m[numbers[i]];
            if(m[numbers[i]]>1) {duplication[0]=numbers[i];return true;}
        }
        return false;
    }
};

发表于 2019-04-19 11:34:10 回复(0)
因为数组长度为n, 整数范围为0~n-1, 所以我们可以直接用这个数组来标记已经出现过的数, 如果再次在某次标记的时候又第二遇到, 那肯定就是有重复了

# -*- coding:utf-8 -*-
class Solution:
    # 这里要特别注意~找到任意重复的一个值并赋值到duplication[0]
    # 函数返回True/False
    def duplicate(self, numbers, duplication):
        # write code here
        cur = 0
        while cur < len(numbers):
            if numbers[cur] == cur:
                cur += 1
                continue
                
            if numbers[cur] == numbers[numbers[cur]]:
                duplication[0] = numbers[cur]
                return True
            
            # 注意这里不能直接multiple assignment
            temp = numbers[cur]
            numbers[cur] = numbers[numbers[cur]]
            numbers[temp] = temp
        return False

发表于 2018-07-19 22:37:59 回复(2)

剑指Offer-数组中重复的数字

package Array;

/**
 * 数组中重复的数字
 *在一个长度为n的数组里的所有数字都在0到n-1的范围内。
 * 数组中某些数字是重复的,但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。
 * 例如,如果输入长度为7的数组{2,3,1,0,2,5,3},那么对应的输出是第一个重复的数字2。
 * 思路:
 * 数组中的数字都在0到n-1的数字范围内。如果数组中没有重复出现的数字,那么当数组排序后数字i就出现在数组中下标为i的元素处。那么数组中如果存在重复数字的话,有些位置的对应的数字就没有出现,而有些位置可能存在多个数字。数组用numbers表示
 那么我们重排这个数组。从第0个元素开始。
 1、比较numbers[i]和i的值,如果i与numbers[i]相等,也就是对数组排序后,numbers[i]就应该在对应的数组的第i个位置处,那么继续判断下一个位置。
 2、如果i和numbers[i]的值不相等,那么判断以numbers[i]为下标的数组元素是什么。
 2.1、如果numbers[numbers[i]]等于numbers[i]的话,那么就是说有两个相同的值了,重复了。找到了重复的数字
 2.2、如果numbers[numbers[i]]不等于numbers[i]的话,那么就将numbers[numbers[i]]和numbers[i]互换。继续进行1的判断。
 3、循环退出的条件是直至数组最后一个元素,仍没有找到重复的数字,数组中不存在重复的数字。
 */
public class Solution02 {
    // 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 static void main(String[] args) {
        int[] arr ={2,3,1,0,2,5,3};
        int[] duplication = {-1};
        duplicate(arr,arr.length,duplication);
        System.out.println(duplication[0]);
    }
    public static boolean duplicate(int numbers[],int length,int [] duplication) {
        if(length<=0||numbers==null){
            return false;
        }
        //判断数组数据是否合法
        for(int i=0;i<length;i++){
            if(numbers[i]<0||numbers[i]>length-1){
                return false;
            }
        }

        for(int i=0;i<length;i++){
            while(numbers[i]!=i){
                if(numbers[i]==numbers[numbers[i]]){
                    duplication[0] = numbers[i];
                    return true;
                }else{
                    //交换numbers[i]和numbers[numbers[i]]
                    int temp = numbers[i];
                    numbers[i] = numbers[temp];
                    numbers[temp] = temp;
                }
            }
        }
        return false;
    }
}
发表于 2018-04-17 12:56:43 回复(2)
Ron头像 Ron
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map.Entry;
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
	boolean duplicate(int numbers[],int length,int [] duplication) {
		HashMap<Integer, Integer> countMap = new HashMap<Integer, Integer>();
		if(length < 2||numbers==null){
			return false;
		}
		int j = 1;
		for(int i = 0;i < length;i++){
			if(countMap.get(numbers[i]) == null){
				j = 1;
				countMap.put(numbers[i], j);
			}else{
				j = countMap.get(numbers[i]);
				j++;
				countMap.put(numbers[i], j);
			}
		}
		Iterator iter = countMap.entrySet().iterator();
		while(iter.hasNext()){
			Entry<Integer, Integer> entry = (Entry<Integer, Integer>) iter.next();
			Integer key = entry.getKey();
			Integer val = countMap.get(key);
			if(val > 1){
				duplication[0] = key;
				//	              System.out.println("first:"+num1[0]);
				return true;
			}
		}
		return false;
	}
}

发表于 2015-07-11 15:33:49 回复(2)
有人遇到和我一样的问题吗?
测试用例:
[2,1,3,1,4]

对应输出应该为:

"true,[1]"

你的输出为:

"true,1"
发表于 2017-06-10 20:48:19 回复(9)
用HashMap记录数组中每个元素出现的次数。
然后迭代数组,通过HashMap找出第一个有重复元素的元素。

import java.util.HashMap;

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 (length < 2 || numbers == null) {
            return false;
        }
        // 是否有重复值
        boolean isSuccess = false;
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < length; i++) {
            if (!map.containsKey(numbers[i])) {
                map.put(numbers[i], 1);
            } else {
                int b = map.get(numbers[i]);
                map.put(numbers[i], b+1);
                isSuccess = true;
            }
        }
        for (int i = 0; i < length; i++) {
            if (map.get(numbers[i]) > 1){
                duplication[0] = numbers[i];
                return isSuccess;
            }
        }
        return isSuccess;
    }
}

发表于 2018-08-11 01:48:27 回复(1)
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 == 0){
            return false;
        }
        for(int i = 0 ; i < length;i++){
            if(numbers[i] < 0 || numbers[i]>length - 1){
                return false;
            }
        }
        for(int i = 0 ; i < length;i++){
            while(numbers[i] != i){
                if(numbers[i] == numbers[numbers[i]]){
                    duplication[0] = numbers[i];
                    return true;
                }
                int temp = numbers[i];
                numbers[i] = numbers[temp];
                numbers[temp] = temp;
            }
        }
        return false;
    }
}

为什么最后交换的部分使用位运算会超时?
发表于 2018-08-01 20:24:47 回复(1)