面试题 03. 数组中重复的数字

题目描述

找出数组中重复的数字。


在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。

示例 1：

输入：
[2, 3, 1, 0, 2, 5, 3]
输出：2 或 3

 

限制：

2 <= n <= 100000

解法

解法一：排序

我们可以先对数组 nums 进行排序，然后遍历排序后的数组，判断相邻的两个元素是否相等，如果相等，即找到了一个重复的数字，返回该数字即可。

时间复杂度 (O(n \log n))，空间复杂度 (O(\log n))。其中 (n) 是数组 nums 的长度。

Python3 实现

1
2
3
4
5
6
7
class Solution:
    def findRepeatNumber(self, nums: List[int]) -> int:
        nums.sort()
        for i in range(1, len(nums)):
            if nums[i] == nums[i - 1]:
                return nums[i]
        return -1  # 理论上不会执行到这里，因为题目保证有重复数字

Java 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
import java.util.Arrays;

class Solution {
    public int findRepeatNumber(int[] nums) {
        Arrays.sort(nums);
        for (int i = 1; i < nums.length; ++i) {
            if (nums[i] == nums[i - 1]) {
                return nums[i];
            }
        }
        return -1;  // 理论上不会执行到这里，因为题目保证有重复数字
    }
}

解法二：哈希表

我们可以使用哈希表来解决这个问题，遍历数组 nums，对于遍历到的每个元素，判断哈希表中是否存在该元素，如果哈希表中存在该元素，即找到了一个重复的数字，返回该数字即可；如果哈希表中不存在该元素，将该元素加入哈希表中。继续遍历，直到找到一个重复的数字。

时间复杂度 (O(n))，空间复杂度 (O(n))。其中 (n) 是数组 nums 的长度。

Python3 实现

1
2
3
4
5
6
7
8
class Solution:
    def findRepeatNumber(self, nums: List[int]) -> int:
        seen = set()
        for num in nums:
            if num in seen:
                return num
            seen.add(num)
        return -1  # 理论上不会执行到这里，因为题目保证有重复数字

Java 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
import java.util.HashSet;
import java.util.Set;

class Solution {
    public int findRepeatNumber(int[] nums) {
        Set<Integer> seen = new HashSet<>();
        for (int num : nums) {
            if (!seen.add(num)) {
                return num;
            }
        }
        return -1;  // 理论上不会执行到这里，因为题目保证有重复数字
    }
}

解法三：原地交换

我们可以遍历数组 nums，对于遍历到的每个元素 nums[i]，判断 nums[i] 是否等于 i，如果是，则继续遍历下一个元素；如果不是，则将 nums[i] 与 nums[nums[i]] 进行交换，交换之后，nums[i] 的值和下标都发生了改变，如果 nums[i] 与 nums[nums[i]] 相等，即找到了一个重复的数字，返回该数字即可；如果 nums[i] 与 nums[nums[i]] 不相等，继续遍历，直到找到一个重复的数字。

时间复杂度 (O(n))，空间复杂度 (O(1))。其中 (n) 是数组 nums 的长度。

Python3 实现

1
2
3
4
5
6
7
8
class Solution:
    def findRepeatNumber(self, nums: List[int]) -> int:
        for i in range(len(nums)):
            while nums[i] != i:
                if nums[nums[i]] == nums[i]:
                    return nums[i]
                nums[nums[i]], nums[i] = nums[i], nums[nums[i]]
        return -1  # 理论上不会执行到这里，因为题目保证有重复数字

Java 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int findRepeatNumber(int[] nums) {
        for (int i = 0; i < nums.length; ++i) {
            while (nums[i] != i) {
                if (nums[nums[i]] == nums[i]) {
                    return nums[i];
                }
                int temp = nums[i];
                nums[i] = nums[nums[i]];
                nums[nums[i]] = temp;
            }
        }
        return -1;  // 理论上不会执行到这里，因为题目保证有重复数字
    }
}

这三种方法都能够有效地找到数组中任意一个重复的数字。根据具体需求和约束条件，可以选择合适的方法来实现。

License

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。

Share