首页 > 试题广场 >

数组中重复的数字

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

热度指数：166349 时间限制：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都是对的

算法知识视频讲解

Java

在看机会的小黄鸭

public int duplicate (int[] numbers) {
        // write code here
        int left = 0;
        int length = numbers.length;
        while(left<length){
            int right = left+1;
            while(right<length){
                if(numbers[left]==numbers[right]){
                    return numbers[left];
                }
                right++;
            }
            left++;
        }
        return -1;
    }

双指针法

编辑于 2024-03-29 21:36:02 回复(0)

Java

Sirena

public static int duplicate(int[] numbers) {

// write code here

int len=numbers.length;

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

if(numbers[j]==0){

numbers[j]=-1;

}

int a[]=new int[numbers.length];

for(int b:numbers){

if (b==-1){

a[0]=1;

}

else if(a[b]!=0){

return b;

}

else{

a[b]=1;

}

return -1;

}

发表于 2023-08-29 10:32:20 回复(1)

Java

SUMMERENT

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

发表于 2023-06-14 09:28:30 回复(0)

Java

嵩山淞湖

public int duplicate (int[] numbers) {

// write code here

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

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

if(map.containsKey(numbers[i])){

return numbers[i];

}

map.put(numbers[i],0);

}

return -1;

}

直接使用HashMap进行标记，每次循环的时候查询key值，如果包含则返回这个值，否则就保存其kv，这个方法还可以应对本题的另一种形式：找出出现次数最多/第二多的数字，这时只要对map的value进行操作即可

发表于 2023-05-15 20:29:47 回复(0)

Java

肉豆蔻吖

import java.util.*;


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

        for (int i = 0; i < length; i++) {
            if (list.contains(numbers[i])) {
                return numbers[i];
            }
            list.add(numbers[i]);
        }
        
        return -1;
    }
}

发表于 2023-05-11 09:35:44 回复(0)

Java

Hadoopdoop

public class Solution {

    public int duplicate (int[] numbers) {
        HashSet<Integer> set = new HashSet<>();
        for (int i = 0; i < numbers.length; i++) {
            if (set.contains(numbers[i])) {
                return numbers[i];
            }else {
                set.add(numbers[i]);
            }
        }
        return -1;
    }
}

发表于 2023-03-10 17:00:00 回复(0)

Java

牛客877628353号

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 采用散列的方式，散列槽足够大，冲突的就是重复的。（布隆过滤器）
     * 
     * @param numbers int整型一维数组 
     * @return int整型
     */
    public int duplicate (int[] numbers) {
        // 通过一个散列函数，映射对应的空间
        int size = numbers.length;
    
        int[] numbersCopy = new int[size];
        for(int i = 0; i<size;i++){
            int num = numbers[i];
            if(num > 10000){
                return -1;
            }
            int index = num%10000;
            System.out.println("实际值："+index+numbersCopy[index]);
            if(numbersCopy[index] == 100001){
                return num;
            }else{
                numbersCopy[index] = 100001;
            }
        }
        return -1;
    }
}

发表于 2023-02-08 00:57:06 回复(0)

Java

牛客162161559号

    public int duplicate (int[] numbers) {
        //这种思路下，无需对数组排序，性能差不多
        int n = 0;
        if(numbers.length < 1) {
            return -1;
        }
        //直接拿第一个依次往后循环比较，不符合就换下一个
        while (true) {
            for (int i = n + 1; i < numbers.length; i++ ) {
                if (numbers[i] == numbers[n]) {
                    return numbers[n];
                }
                //但比较到最后一个元素，说明没有重复元素
                if (n == numbers.length-1) {
                    return -1;
                }
            }
            n++;
        }
    }

发表于 2022-11-25 20:02:32 回复(0)

Java

小L努力拿offer

import java.util.*;

public class Solution {

/**

* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可

* @param numbers int整型一维数组

* @return int整型

public int duplicate (int[] numbers) {

if(numbers == null || numbers.length == 0){

return -1;

}

HashSet<Integer> hashSet = new HashSet<>();

for(int i : numbers){

if(i < numbers.length){

if(hashSet.contains(i)){

return i;

}else{

hashSet.add(i);

}

}else{

return -1;

}

发表于 2022-11-23 01:52:07 回复(1)

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)

Java

牛客447217979号

思路：暴力求，时间69ms，内存12864kb。

先对数组进行排序，利用java中的工具类，Arrays.sort。在排序数组的基础上，如果连续有两个数据是相等的，则返回这个数据，否则返回-1。

public int duplicate(int[] numbers){

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

发表于 2022-08-19 11:11:37 回复(0)

Java

牛客461316693号

import java.util.*;


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

发表于 2022-08-16 16:30:46 回复(0)

Java

GoIn

该题的解题思路:

一:长度为n,其中包含0~n-1之间的数

二:如果无重复,则数字排序后的下标应该与元素一一对应

解题步骤:

1.遍历数组,先判断该元素是否与下标相同,如果相同,则跳过该次循环.

2.如果数组元素与下标不相同,就将其交换到属于他的位置,在交换前检查该元素

在它原本的位置是否有一个相同的元素,如果有,则重复了,就返回该元素,

3.如果遍历完,无重复,则返回-1

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param numbers int整型一维数组 
     * @return int整型
     */
    public int duplicate (int[] numbers) {
        // write code here
        for(int i = 0;i<numbers.length;i++){
            //如果元素与下标相同则跳过该次循环
           if(numbers[i] == i){
               continue;
           } else{
               //判断是否出现重复的元素.如果为true,则返回该元素
               if(numbers[i] == numbers[numbers[i]]){
                   return numbers[numbers[i]];
               }
           }
            //进行元素交换
            int temp = numbers[i];
            numbers[i] = numbers[temp];
            numbers[temp] = temp;
        }
        //数组有错误或者该数组为有序数组(无重复)
        return -1;
    }
}

发表于 2022-08-06 15:06:37 回复(0)

Java

哎哎唉唉诶诶

public int duplicate (int[] numbers) {
        int n=numbers.length;
        //dp[number[i]] 记录第 number[i]是否已存在 0/1
        int[] dp=new int[n];
        for(int i=0;i<n;i++){
            //题目意思要我们自测numbers数组是否合法[0,n-1]
            if(numbers[i]>n-1||numbers[i]<0){
                return -1;
            }
            dp[i]=0;
        }
         for(int i=0;i<n;i++){
            if(dp[numbers[i]]==0){
                dp[numbers[i]]=1;
            }else{
                return numbers[i];
            }
        }
        return -1;
        
    }

发表于 2022-08-05 21:40:48 回复(0)

Java

勇敢牛牛不怕难

import java.util.*;


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

发表于 2022-08-04 22:40:07 回复(0)

Java

牛客265940881号

import java.util.Scanner;

public class t1 {
	public static void main(String[] args) {
		Scanner input=new Scanner(System.in);
		String string=input.nextLine();
		string=string.replace("[", "");
		string=string.replace("]", "");
		String[] strings=string.split(",");
		System.out.println(find(strings));
		
	}
	public static String find(String[] strings) {
		for (int i = 0; i < strings.length; i++) {
			for (int j = i+1; j < strings.length-1; j++) {
				if (strings[i].equals(strings[j])) {
					return strings[i];
				}
			}
			
		}
		return "-1";
	}
}

本地通过，为什么编译不过？求大佬解答

发表于 2022-08-01 09:55:28 回复(1)