LeetCode.645.Set Mismatch 找出数组中重复的数和缺失的数

题目描述

645 Set Mismatch
https://leetcode-cn.com/problems/set-mismatch/

The set S originally contains numbers from 1 to n. But unfortunately, due to the data error, one of the numbers in the set got duplicated to another number in the set, which results in repetition of one number and loss of another number.

Given an array nums representing the data status of this set after the error. Your task is to firstly find the number occurs twice and then find the number that is missing. Return them in the form of an array.

Example 1:

Input: nums = [1,2,2,4]
Output: [2,3]

Note:
The given array size will in the range [2, 10000].
The given array’s numbers won’t have any order.

---

解题过程

相似题目
LeetCode.448.Find All Numbers Disappeared in an Array 数组中消失的数
LeetCode.442.Find All Duplicates in an Array 数组中所有重复的数
LeetCode.645.Set Mismatch 找出数组中重复的数和缺失的数
LeetCode.041.First Missing Positive 数组中缺失的第一个正数

一看到题干中的 1 ≤ a[i] ≤ n ，就知道肯定是用数组下标技巧做。
原地哈希，在输入数组本身以某种方式标记已访问过的数字，对于数据中的每个值 a[i] ，将值 a[a[i]] 取反来表示这个值出现过 。

时间复杂度 O(n)，空间复杂度 O(1)

private static class SolutionV2020 {
    public int[] findErrorNums(int[] nums) {
        int[] res = new int[2];
        for (int i = 0; i < nums.length; i++) {
            // 重复的值
            if (nums[Math.abs(nums[i]) - 1] < 0) {
                res[0] = Math.abs(nums[i]);
            } else {
                // 已出现值的下标改为负的
                nums[Math.abs(nums[i]) - 1] = - nums[Math.abs(nums[i]) - 1];
            }
        }

        for (int i = 0; i < nums.length; i++) {
            // 值为正的表示他的下标没出现过
            if (nums[i] > 0) {
                res[1] = i + 1;
            }
        }
        return res;
    }
}

---

GitHub代码

algorithms/leetcode/leetcode/_645_SetMismatch.java
https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_645_SetMismatch.java

---