645. Set Mismatch

Problem:

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]

Analysis:
这道题我只能做到count 出现的次数。其他方法太数学了想不出来。这里可以数组来计数，速度更快。

Solution:
1. Count

class Solution {
    public int[] findErrorNums(int[] nums) {
        int[] res = new int[2];
        int[] count = new int[nums.length];
        for (int i: nums) {
            ++count[i - 1];
        }
        for (int i = 0; i < nums.length; i++) {
            if (res[0] != 0 && res[1] != 0)
                return res;
            if (count[i] == 2) res[0] = i + 1;
            if (count[i] == 0) res[1] = i + 1;
        }
        return res;
    }
}

2. Use boolean array
First loop, set very item to true. If a index is already true, we can tell that it's dup.
Second loop, if we find out that set[i] is still false, we can know that i + 1 is missing number.

class Solution {
    public int[] findErrorNums(int[] nums) {
        int dup = 0;
        boolean[] set = new boolean[nums.length + 1];
        for (int num : nums) {
            if (set[num]) {
                dup = num;
            }
            set[num] = true;
        }
        for (int i = 1; ; i++) {
            if (!set[i]) return new int[] {dup, i};
        }  
    }
}