[数组]645. Set Mismatch

题目：645. 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.

一个数组含有1到n的数组，然而里面有一个数字重复了使得另一个数字缺失了，找到这两个数字。数组无排序，size一定。

用了一个很笨的办法。遍历第一遍找出重复的数字，并把不重复的数字加入set。再遍历一遍set找出那个缺失的数字。效率一般。

class Solution {
    public int[] findErrorNums(int[] nums) {
        int len = nums.length;
        int[] res = new int[2];
        if(len == 0) return res;
        Arrays.sort(nums);
        Set<Integer> set = new HashSet<Integer>();
        for(int i = 1; i <= len ; i++){
            if(set.contains(nums[i-1])){
                res[0] = nums[i-1];
            }else{
                set.add(nums[i-1]);
            }
        }
        for(int i = 1;i<= len ;i++){
            if(!set.contains(i)){
                res[1] = i;
                break;
            }
        }
        return res;
    }
}

solution里优秀的解法：
都不需要排序。

class Solution {
    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]);//遇到重复的index，该nums［index －1］ 已为负
            }
            else {
                nums[Math.abs(nums[i]) - 1] *= -1; //将所有不重复的数作index的位为标为－;
            }
        }
        for(int i = 0 ; i < nums.length ; i++) {
            if(nums[i] > 0) {
                res[1] = i + 1; //未被标记的index即为缺失的index
            }
        }
        return res;
    }

}

更高级的解法：

class Solution {
    public int[] findErrorNums(int[] nums) {
        int[] occur = new int[nums.length];
        int dup = 0, miss = 0;
        for (int n : nums) {
            occur[n-1]++;
            if (occur[n-1] == 2) dup = n;
        }
        for (int i = 0;i < nums.length;i++) {
            if (occur[i] == 0) miss = i+1;
        }
        
        return new int[]{dup, miss};
    }
}