关于leetcode:每日一练1找出数组中重复的数字

title: 每日一练（1）：找出数组中反复的数字

categories:[剑指 offer]

tags:[每日一练]

date: 2022/01/12

每日一练（1）：找出数组中反复的数字

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

示例 1：

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

限度：

2 <= n <= 100000

起源：力扣（LeetCode）
链接：https://leetcode-cn.com/probl…

办法一：哈希表

算法流程：

• 初始化：新建 Hash
• Set，记为 dicdic；
• 遍历数组 numsnums 中的每个数字 numnum：
• 当 numnum 在 dicdic 中，阐明反复，间接返回 numnum；
• 将 numnum 增加至 dicdic 中；
• 返回 -1−1。本题中肯定有反复数字，因而这里返回多少都能够。

复杂度剖析：

• 工夫复杂度 O(N)O(N)：遍历数组应用 O(N)O(N)，HashSet 增加与查找元素皆为 O(1)O(1)。
• 空间复杂度 O(N)O(N)：HashSet 占用 O(N)O(N) 大小的额定空间。

int findRepeatNumber(vector<int>& num) {
    unordered_map<int, bool> map;
    for (int num : nums) {    // 循环遍历
        if (map[num]) {return num;}
        map[num] = true;
    }
    return -1;
}

办法 2：原地替换

算法流程：

• 1. 遍历数组 numsnums，设索引初始值为 i = 0i=0 :

  • 1. 若 nums[i] = inums[i]=i：阐明此数字已在对应索引地位，无需替换，因而跳过；
  • 2. 若 nums[nums[i]] = nums[i]nums[nums[i]]=nums[i]：代表索引 nums[i]nums[i] 处和索引 ii 处的元素值都为 nums[i]nums[i]，即找到一组反复值，返回此值 nums[i]nums[i]；
  • 3. 否则：替换索引为 ii 和 nums[i]nums[i] 的元素值，将此数字替换至对应索引地位。
• 2. 若遍历结束尚未返回，则返回 -1−1。

复杂度剖析：

• 工夫复杂度 O(N)O(N)：遍历数组应用 O(N)O(N)，每轮遍历的判断和替换操作应用 O(1)O(1)。
• 空间复杂度 O(1)O(1)：应用常数复杂度的额定空间。

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