微信公众号:路人zhang
扫码关注微信公众号

回复“面试手册”,获取本站PDF版

回复“简历”,获取高质量简历模板

回复“加群”,加入程序员交流群

回复“电子书”,获取程序员类电子书

当前位置: 算法 > 剑指offer > 03. 数组中重复的数字

题目描述

找出数组中重复的数字。

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

示例 1:

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

限制:

2 <= n <= 100000


算法 1

(哈希表) O(n)

遍历数组,判断当前数是否在哈希表中,如果在则当前数就是一个重复的数,直接返回,否则将当前数加入到哈希表中。

时间复杂度

O(n)

空间复杂度

O(n)

C++ 代码

class Solution {
public:
    int findRepeatNumber(vector<int>& nums) {
        unordered_map<int, int> hash;
        for (auto x : nums) {
            if (hash.count(x)) return x;
            hash[x] ++ ;
        }
        return -1;
    }
};

Java 代码

class Solution {
    public int findRepeatNumber(int[] nums) {
        Map<Integer, Integer> hash = new HashMap<>();
        for (int x : nums) {
            if (hash.containsKey(x)) {
                return x;
            }
            hash.put(x, hash.getOrDefault(x, 0) + 1);
        }
        return -1;
    }
}

Python 代码

class Solution:
    def findRepeatNumber(self, nums: List[int]) -> int:
        hash = {}
        for x in nums:
            if x in hash:
                return x
            hash[x] = hash.get(x, 0) + 1
        return -1

算法 2

(原地交换) O(n)

题目已知所有数的范围在 [0, n – 1] 之间,且有重复数字,我们把每个数放在它的下标位置上,那么对于重复数字必然会出现它的位置上已经放上了该数字。

根据以上原理,遍历数组,从前往后扫描每个下标 i 和数 nums[i],只要当前下标和数不对应(不相等),则判断下标 nums[i] 和这个下标上的数 nums[nums[i]] 是否对应,如果对应则当前数就是重复数字,直接返回,否则交换这两个数,循环此操作。

时间复杂度

O(n)

空间复杂度

O(n)

C++ 代码

class Solution {
public:
    int findRepeatNumber(vector<int>& nums) {
        for (int i = 0; i < nums.size(); i ++ ) {
            while (nums[i] != i && nums[nums[i]] != nums[i]) swap(nums[i], nums[nums[i]]);
            if (nums[i] != i && nums[nums[i]] == nums[i]) return nums[i];
        }
        return -1;
    }
};

Java 代码

class Solution {
    public int findRepeatNumber(int[] nums) {
        for (int i = 0; i < nums.length; i ++ ) {
            while (nums[i] != i && nums[nums[i]] != nums[i]) {
                int temp = nums[i];
                nums[i] = nums[temp];
                nums[temp] = temp;
            }
            if (nums[i] != i && nums[nums[i]] == nums[i]) {
                return nums[i];
            }
        }
        return -1;
    }
}

Python 代码

class Solution:
    def findRepeatNumber(self, nums: List[int]) -> int:
        for i in range(len(nums)):
            while nums[i] != i and nums[nums[i]] != nums[i]:
                nums[nums[i]], nums[i] = nums[i], nums[nums[i]]
            if nums[i] != i and nums[nums[i]] == nums[i]:
                return nums[i]
        return -1

本文由读者提供Github地址:https://github.com/tonngw


点击面试手册,获取本站面试手册PDF完整版