寻找唯一重复数

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

热度指数：1295 时间限制：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)

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)