我要招人

去企业版

首页 > 试题广场 >

寻找唯一重复数

[编程题]寻找唯一重复数

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

给定一个包含 n 个正整数的数组 nums，数组中所有数字都在区间 [1,n-1] 内，但有一个数出现了两次及以上，其余所有数字都仅出现一次。
例如 [4,2,3,1,4] ，其中 4 出现了两次。

请你找到这个重复的数。

进阶一:

请你找到一个时间复杂度为 $O(nlogn)$ ，空间复杂度为 $O(1)$ 的方法

进阶二:

请你找到一个时间复杂度为 $O(n)$ ，空间复杂度为 $O(1)$ 的方法

数据范围： $1 \le n \le 10^5 \$

示例1

输入

[4,2,1,3,3]

输出

示例2

输入

[1,2,3,4,5,6,7,8,9,9]

输出

算法知识视频讲解

Java

skwan

标记法：时间复杂度O(n)，空间复杂度O(1)

import java.util.*;


public class Solution {

    public int findRepeatNum (ArrayList<Integer> nums) {
        int n = nums.size();
        for (int i = 0; i < n; i++) {
            int cur = Math.abs(nums.get(i));
            if (nums.get(cur) < 0) return cur;
            nums.set(cur, 0 - nums.get(cur));
        }
        return -1;
    }
}

发表于 2022-07-17 09:43:16 回复(0)

Python 3

danspace

class Solution:
    def findRepeatNum(self , nums: List[int]) -> int:
        # write code here
        d = {}
        for n in nums:
            if n in d:
                return n
            else:
                d[n] = 1

发表于 2022-04-22 15:08:05 回复(0)

C++

一品统合

将数值视作索引，索引对应位置的元素设为相反数，表示出现过一次。

如果发现某个位置的元素已经是负的，那么表示已经出现过一次，现在遇到第二次。

class Solution {
public:
    /**
     */
    int findRepeatNum(vector<int>& nums) {
        int i = 0;
        for (; i < nums.size(); i++) {
            if (nums[abs(nums[i]) - 1] > 0) {
                nums[abs(nums[i]) - 1] *= -1;
            } else {
                break;
            }
        }
        return abs(nums[i]);
    }
};

发表于 2023-05-24 18:24:13 回复(0)

小谷围做题家

package main
//import "fmt"

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param nums int整型一维数组 
 * @return int整型
*/
func findRepeatNum( nums []int ) int {
    cnt:=map[int]int{}
    for _,n:=range nums{
        if _,ok:=cnt[n];ok{
            return n
        }
        cnt[n]++
    }
    return -1
}

发表于 2023-03-28 20:12:45 回复(0)

一公升的眼泪

function findRepeatNum( nums ) {
        // 找环入口
    let  slow = 0, fast = 0;
    do{
        //快指针走两步，慢指针走一步
        slow = nums[slow];
        fast = nums[nums[fast]];
    }while(slow != fast);
    slow=0;
    while(nums[slow] !== nums[fast]){
        fast = nums[fast];
        slow = nums[slow];
    }
    return nums[slow];
}
module.exports = {
    findRepeatNum : findRepeatNum
};

发表于 2022-08-05 22:56:13 回复(0)

C++

言秋

环形链表，找入口节点

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @return int整型
     */
    int findRepeatNum(vector<int>& nums) {
        // write code here
        int slow=0,fast=0;
        slow=nums[slow];
        fast=nums[nums[fast]];
        while(slow!=fast){
            slow=nums[slow];
            fast=nums[nums[fast]];
        }
        slow=0;
        while(slow!=fast){
            slow=nums[slow];
            fast=nums[fast];
        }
        return slow;
    }
};

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

Java

菲尼克斯弗兰克

// 利用符号 原地哈希
import java.util.*;
public class Solution {
    // 原地哈希
    public int findRepeatNum (ArrayList<Integer> nums) {
        for (int i = 0; i < nums.size(); i++) {
            int idx = Math.abs(nums.get(i));
            if (nums.get(idx) > 0) {
                nums.set(idx, nums.get(idx)*-1);
            } else {
                return idx;
            }
        }
        return -1;
    }
}

发表于 2022-05-03 16:43:47 回复(0)

Python

牛客961048420号

#coding:utf-8
#思路还是用字典最简单，遍历列表把每个数出现的数次用字典存储下来，再遍历字典，看看哪个数的次数不等于1的。
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param nums int整型一维数组
# @return int整型
#
class Solution:
def findRepeatNum(self , nums ):
# write code here
d={}
for i in nums:
d[i]=d.get(i,0)+1
for i in d:
if d[i]!=1:
return i

发表于 2022-04-10 00:12:52 回复(0)