LeetCode 645 - Set Mismatch

https://leetcode.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:

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

O(1) space
https://discuss.leetcode.com/topic/96808/java-o-n-time-o-1-space

https://discuss.leetcode.com/topic/96945/java-two-methods-using-sign-and-swap

Method 1 is to put each element k to the k-1th position unless the k-1th is already occupied by k. In that case we know k is a duplicate. In a second pass, we look for the ith position where its value is not i+1, we know i+1 is the missing value.

    private void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }

    public int[] findErrorNums(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            while (nums[nums[i]-1] != nums[i]) {
                swap(nums, i, nums[i]-1);
            }
        }
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != i+1) return new int[]{nums[i], i+1};
        }
        return null;
    }

Method 2: when we encounter a value k, we set the k-1th element negative. If k-1th is already negative we know k is the duplicate. In the second pass we look for ith position where it's value is positive so we know i+1 is the missing one.

https://discuss.leetcode.com/topic/96828/very-simple-using-array-and-bit

Using Array Indexing:

public int[] findErrorNums(int[] nums) {
      int[] arr = new int[nums.length+1];
      int a=0,b=arr.length;       
      for(int i: nums) arr[i]++;
        
      for(int j=1;j<arr.length;j++){
          if(arr[j]==2) a=j;
          if(arr[j]==0) b=j;            
      }
      return new int[]{a,b};
}

Using Bit:

public int[] findErrorNums(int[] nums) {
    BitSet bs = new BitSet(nums.length+1);
    int a=0;
    for(int i:nums){
          if(bs.get(i)) a=i;
          bs.set(i);            
    }
    return new int[]{a,bs.nextClearBit(1)};
}

https://discuss.leetcode.com/topic/96806/simple-java-o-n-solution-hashset

Idea is to compute the sum mathematically first, and subtracting the elements from it.
Find the duplicate element, and add that to sum.

public int[] findErrorNums(int[] nums) {
    Set<Integer> set = new HashSet<>();
    int duplicate = 0, n = nums.length;
    long sum = (n * (n+1)) / 2;
    for(int i : nums) {
        if(set.contains(i)) duplicate = i;
        sum -= i;
        set.add(i);
    }
    return new int[] {duplicate, (int)sum + duplicate};
}

X. Videos
【每日一题：小Fu讲解】LeetCode 645. Set Mismatch