首页 > 试题广场 >

数组中重复的数字

[编程题]数组中重复的数字
  • 热度指数：171827 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如，如果输入长度为7的数组[2,3,1,0,2,5,3]，那么对应的输出是2或者3。存在不合法的输入的话输出-1

数据范围：
进阶：时间复杂度，空间复杂度
示例1

输入

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

输出

2

说明

2或3都是对的
算法知识视频讲解
添加回答
Java
୧⍢⃝୨头像 ୧⍢⃝୨ 
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.contains(numbers[i])) {
                return numbers[i];
            }
            set.add(numbers[i]);
        }
        return -1;
    }
}

发表于 2024-08-06 16:26:01 回复(0)
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头像 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头像 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
_ther头像 _ther 
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头像 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号头像 牛客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号头像 牛客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头像 小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号头像 牛客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号头像 牛客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头像 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)
提交观点

问题信息

数组
上传者：牛客301499号
难度：
64条回答 8028浏览

热门推荐

通过挑战的用户

查看代码

相关试题

数组中重复的数字

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号