算法1.数组中重复的数字

题目描述

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

示例 1：

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

解题思路

方法一：原地置换

时间复杂度：$O(N)$

空间复杂度：$O(1)$

代码如下

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

解法分析

主要思路在于将数组index和相应的value对应起来。在while循环体内，每个值至多通过两次（多数是一次）交换，规划到相应的位置。因此时间复杂度为$O(N)$

解法注意点

• while循环的复杂度需要均摊分析
• 如果要求不改变原数组，则此方法无效
• 如果题目没有规定 「所有数字都在 0～n-1 的范围内」，则此方法无效。（考虑数组空间）
• 做题的时候，需要考虑时间复杂度、空间复杂度、是否可以改变原数组等。

方法二：Hash映射法

时间复杂度：$O(N)$

空间复杂度：$O(N)$

代码如下

class Solution {
public:
    int findRepeatNumber(vector<int>& nums) {
        unordered_map<int, bool> map;
        for(int num : nums) {
            if(map[num]) return num;
            map[num] = true;
        }
        return -1;

    }
};

解法分析

通过map映射，将数字逐个放到hash表里，若某个数之前hash没有，则值true；若某个数之前hash存在，即映射过程中发现值为true，则可以判断重复。