首页 > 试题广场 >

数组中重复的数字

[编程题]数组中重复的数字

热度指数：171827 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

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

数据范围： $0\le n \le 10000 \$

进阶：时间复杂度 $O(n)\$ ，空间复杂度 $O(n)\$

示例1

输入

[2,3,1,0,2,5,3]

输出

说明

2或3都是对的

算法知识视频讲解

神秘码仔Orange

直接使用java的set特性来实现

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param numbers int整型一维数组 
     * @return int整型
     */
    public int duplicate (int[] numbers) {
        HashSet<Integer> set = new HashSet<>();
        for (int i = 0; i < numbers.length; i++) {
            if (!set.add(numbers[i])) {
                return numbers[i];
            }
        }
        return -1;
    }
}

发表于 2021-02-25 22:13:02 回复(4)

1666

数组中重复的数字-替换法（O(n),O(1)）

    //解题思路
    /*替换法（O(n),O(1)）
    数组存放原则：numbers[i] = i
    遍历数组所有元素，交换不符合数组存放原则的元素：
        例如[2,3,1,0,2]
        遍历0位元素2：（交换0位元素2和2位元素1）->[1,3,2,0,2]
        遍历0位元素1：（交换0位元素1和1位元素3）->[3,1,2,0,2]
        遍历0位元素3：（交换0位元素3和3位元素0）->[0,1,2,3,2]
        依次遍历0、1、2、3位置元素，都符合存放原则numbers[i] = i，不做任何操作
        遍历末位元素2，此时末位元素2和2位元素2相等，出现了两次，即数字2位重复元素
     */
    public int duplicate (int[] numbers) {
        for (int i = 0; i < numbers.length; i++) {
            if (numbers[i] != i){
                if (numbers[i] == numbers[numbers[i]]) return numbers[i];
                int temp = numbers[numbers[i]];
                numbers[numbers[i]] = numbers[i];
                numbers[i] = temp;
                i--;//遍历完0位元素以及交换完数字后，如果0位元素仍不符合数组存放原则：numbers[i] = i，那么还要重新遍历0位元素
            }
        }
        return -1;
    }

发表于 2021-03-26 23:06:58 回复(10)

HelloW1

#利用Hashmap结构保存数组，Boolean用于表示某一数字是否重复，最后遍历hashmap

import java.util.*;

public class Solution {
    public int duplicate (int[] numbers) {
        int len=numbers.length;
        if(len==0 ||len==1)
            return -1;
        HashMap<Integer,Boolean> map=new HashMap<Integer,Boolean>();
        for(int i=0;i<len;i++){
            //若已存在，则插入为true，否则插入为false
            map.put(numbers[i],map.containsKey(numbers[i]));
        }
        for(int i=0;i<len;i++){
            if(map.get(numbers[i]))
                return numbers[i];
        }
        return -1;
    }
}

发表于 2021-02-27 10:30:24 回复(2)

Java

贺沛hopeplus

java 数组判断

public int duplicate (int[] numbers) {
        // write code here
        int n = numbers.length;
        int[] res = new int[n];
        for (int i : numbers) {
            res[i]++;
             if (res[i] > 1) {
                return i;
            }
        }
        return -1;
    }

发表于 2021-04-28 11:41:53 回复(5)

C++

Dan_na

    int duplicate(vector<int>& numbers) {
        int len=numbers.size();
        for (int i=0; i<len; i++)
        {
            for(int j=i+1; j<len; j++)
            {
                if(numbers[i]==numbers[j])
                    return numbers[i];
            }
        }
        return -1;

真正纯小白解题

发表于 2021-08-13 16:52:28 回复(3)

Python

陌上谁家少年足风流

创建一个空的集合，然后遍历列表中的元素，当集合中没有这个元素时,就在集合中添加这个元素，如果有这个元素，就return

class Solution:
    def duplicate(self , numbers ):
        jihe=set()
        for i in numbers:
            if i not in jihe:
                jihe.add(i)
            else:
                return i
        return -1

发表于 2021-03-24 14:00:58 回复(0)

C/C++

w浩

直接使用map，遍历一遍数组，当第一次出现重复的值时，此时map值大于1，直接返回得到答案

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param numbers int整型vector 
     * @return int整型
     */
    int duplicate(vector<int>& numbers) {
        if(numbers.size()<=1) return -1;
        // write code here
        unordered_map<int,int> map;
        for(int i = 0;i<numbers.size();i++){
            map[numbers[i]]++;
            if(map[numbers[i]]>1) return numbers[i];
            
        }
        return -1;
    }
};

发表于 2021-03-02 21:28:48 回复(1)

铺洒日光

不需要加一个判断，判断元素值是不是在0-n-1之间吗，这个情况也会返回-1

发表于 2021-04-27 11:43:58 回复(1)

良人久在

    public static int duplicate (int[] numbers) {
        // write code here
    	int[] countarray=new int[numbers.length];
    	for(int i=0;i<numbers.length;i++) {
    		countarray[numbers[i]]++;
    		if(countarray[numbers[i]]>1) {
    			return numbers[i];
    		}
    		
    	}
    	return -1;
    }

发表于 2021-02-26 12:31:49 回复(1)

谁看见我的大白菜了

替换法

class Solution:
    def duplicate(self , numbers ):
        # write code here
        if not numbers:
            return -1
        n = len(numbers)
        for i in range(n):
            v = numbers[i]
            if v < 0:
                v += n
            if numbers[v] < 0:
                return v
            numbers[v] -= n
        return -1

时间复杂度O(N)，除了原数据不消耗额外空间。

发表于 2021-02-26 10:17:15 回复(2)

Python3

啥也不会moon

class Solution:
    def duplicate(self , numbers: List[int]) -> int:
        # write code here
        n = len(numbers)
        for i in range(n):
            if numbers[i] in numbers[0:i]+numbers[i+1:n]:
                return numbers[i]
        return -1

发表于 2023-03-28 16:06:02 回复(0)

Java

圣光·明流火

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param numbers int整型一维数组 
     * @return int整型
     */
    public int duplicate (int[] numbers) {
        // write code here
        //Set数组
        Set<Integer> set = new HashSet<>();
        for(int i = 0;i < numbers.length;i++){
            if(!set.add(numbers[i])){
                return numbers[i];
            }
        }
        return - 1;
    }
}

发表于 2022-08-24 17:02:22 回复(0)

牛客嗷嗷

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param numbers int整型一维数组
     * @return int整型
     */
    public int duplicate (int[] numbers) {
        // write code here
        HashSet<Integer> set = new HashSet<>();
        for (int n : numbers)
            if (set.contains(n))
                return n;
            else
                set.add(n);
        
        return -1;
    }
}

发表于 2022-07-26 17:38:12 回复(0)

Java

叶虽

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param numbers int整型一维数组 
     * @return int整型
     */
    public int duplicate (int[] numbers) {
        // write code here
        if (numbers.length < 1) {
            return -1;
        }
        
        Arrays.sort(numbers);
        int num = -1;
        for (int i = 0; i < numbers.length; i++) {
            if (i >= numbers.length) {
                return -1;
            }
            if (numbers[i] > numbers.length) {
                return -1;
            }
            
            if (numbers[i] == numbers[i + 1]) {
                return numbers[i];
            }
        }
        return num;
    }
}

发表于 2022-05-28 14:14:28 回复(0)

C++

牛客735193053号

int duplicate(vector<int>& numbers) {
// write code here
unordered_set<int> hashset;
for (int num : numbers) {
if (hashset.end() != hashset.find(num)) return num;
hashset.insert(num);
}
return -1;
}

发表于 2022-03-30 10:53:55 回复(0)

C++

牛客505055808号

class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param numbers int整型vector
* @return int整型
*/
int duplicate(vector<int>& numbers) {
// write code here
vector<int> dp(numbers.size(), 0);
if(numbers.size() < 0)
return -1;
for(int i = 0; i < numbers.size(); i++)
{
dp[numbers[i]]++;
}
for(int i = 0; i < numbers.size(); i++)
{
if(dp[i] >= 2)
return i;
}
return -1;
}
};

发表于 2022-03-07 19:28:29 回复(0)

Python 3

Offer快来找我吧9911

class Solution:
    def duplicate(self , numbers: List[int]) -> int:
            aa=list(set(numbers))
            for i in range(len(aa)):
                while numbers.count(aa[i])>1:
                    return aa[i]
            return -1

发表于 2022-03-06 17:52:31 回复(0)

C++

牛客870770703号

int duplicate(vector<int>& numbers) {
// write code here
set<int> n_set;
for(auto t:numbers){
if(n_set.count(t)) return t;
n_set.insert(t);
}
return -1;
}

发表于 2021-08-20 11:04:23 回复(0)

Java

合肥吴彦祖

先排序直接遍历

public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param numbers int整型一维数组
* @return int整型
*/
public int duplicate (int[] numbers) {

// write code here
Arrays.sort(numbers);
for(int i = 1; i < numbers.length; i++){
if(numbers[i] == numbers[i-1]) return numbers[i];
}
return -1;
}
}

发表于 2021-08-16 22:04:33 回复(1)

Javascript

牛客822067661号

function duplicate( numbers ) {
    let arr = [];
    let sort = numbers.sort((a,b) => a-b);
    for(let i = 0; i < sort.length;i++){
        if(sort[i]==sort[i+1]){
            arr.push(sort[i]);
        }
    }
    let result = Array.from(new Set(arr));
    if(result.length===0){
        return -1
    }
    let random = Math.random()*(result.length)
    return result[Math.floor(random)]
}

发表于 2021-08-11 20:14:53 回复(0)