findErrorNums645.md

错误的集合645

原题

集合 S 包含从1到 n 的整数。不幸的是，因为数据错误，导致集合里面某一个元素复制了成了集合里面的另外一个元素的值，导致集合丢失了一个整数并且有一个元素重复。 给定一个数组 nums 代表了集合 S 发生错误后的结果。你的任务是首先寻找到重复出现的整数，再找到丢失的整数，将它们以数组的形式返回。

示例 1: 输入: nums = [1,2,2,4] 输出: [2,3] 注意:

给定数组的长度范围是 [2, 10000]。 给定的数组是无序的。

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/set-mismatch

---

两种解法

1.辅助数组记录数字出现次数（我的第一解）

public int[] findErrorNums(int[] nums) {
        int[] result = new int[2];
        int[] temp = new int[nums.length + 1]; // temp[i] 代表数字i出现的次数, 注意集合中元素是1~n，所以temp的长度为n+1
        for (int i = 0; i < nums.length; i++) {
            temp[nums[i]]++;
        }
        for (int i = 1; i < temp.length; i++) {
            if (temp[i] == 0)
                result[1] = i;
            if (temp[i] == 2)
                result[0] = i;
        }
        return result;
    }

思路分析：

• 要知道是哪个数字重复了，哪个数字缺失了。需要知道哪个数字出现了两次，哪个数字出现0次，要记录各个数字出现的次数。
• 首先想到可以使用哈希表，但是这里还可以使用数组，因为数组的索引也可以充当数值键。temp[i]的索引i代表这是哪一个数字，temp[i]的值代表这个数字出现的次数。
• 所以先遍历nums记录每个数字出现的次数到temp，再遍历temp找到出现过两次的数字和出现过0次的数字即可。
• 遍历了两个数组，长度均为n，所以时间复杂度为$O(n)$。使用了辅助数组，所以空间复杂度为$O(n)$。

代码解释：

• 第3行，注意集合中元素是1~n，所以temp的长度为n+1。
• 4~5行，遍历nums记录每个数字出现的次数到temp。这里nums[i]为当前出现的数字，所以temp[nums[i]]代表该数字出现的次数要+1。

运行结果：

• 执行用时 :3 ms, 在所有 Java 提交中击败了77.70%的用户
• 内存消耗 :48.8 MB, 在所有 Java 提交中击败了5.62%的用户

2.排序（我的第二解）

public int[] findErrorNums2(int[] nums) {
        Arrays.sort(nums);
        int[] result = new int[2];
        for (int i = 0; i < nums.length - 1; i++) {
            if (nums[i + 1] - nums[i] == 0)
                result[0] = nums[i];
            if (nums[i + 1] - nums[i] == 2)
                result[1] = nums[i] + 1;
        }
        if (result[1] == 0) { // 要特别注意缺失第一个元素或者最后一个元素的情况， 这两种情况都会使得result[1]为初始值0
            if (nums[0] != 1)
                result[1] = 1;
            else result[1] = nums.length;
        }
        return result;
    }

思路分析：

• 不记录每个重复数字出现的次数，我们可以将数组进行排序，因为排序后重复的元素比如相邻，缺失元素的前后两个元素相差2。通过这些特征就可以找到缺失及重复数字：
  • 如果当前元素与后一个元素相等nums[i + 1] - nums[i] == 0，当前元素即为重复元素。
  • 如果当前元素与后一个元素相差2nums[i + 1] - nums[i] == 2,当前元素+1即为缺失元素。
• 但是要注意特殊情况，如果缺失的数字是1或者n，通过nums[i + 1] - nums[i]与0,2的比较就找不到缺失值了。
• 所以在遍历完原数组之后，要判断缺失值是否已经找到（找到的标志就是result[1] != 0），如果没有，就去判断缺失了1还是n。这样才完备。
• 使用了排序，所以时间复杂度为$O(nlog(n))$。

代码解释：

• 第10行，在遍历完后判断缺失值是否已经找到。
• 11~13行，如果没有找到缺失值，说明缺失值是特殊情况1或者n，那么就判断第一个元素是否为1即可。

运行结果：

• 执行用时 :17 ms, 在所有 Java 提交中击败了28.63%的用户
• 内存消耗 :49.3 MB, 在所有 Java 提交中击败了5.62%的用户