This is the fifth day of my participation in the August More text Challenge. For details, see:August is more challenging

645, Set Mismatch- Find the repeated number and the missing number

The question:

You have a set of integers s, which originally contains all the numbers from 1 to n. Unfortunately, due to some error, one of the numbers in s got duplicated to another number in the set, which results in repetition of one number and loss of another number.

You are given an integer array nums representing the data status of this set after the error.

Find the number that occurs twice and the number that is missing and return them in the form of an array.

Example 1:

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

Example 2:

 Input: nums = [1,1]
 Output: [1,2]
Copy the code

Constraints:

  • 2 <= nums.length <= 10^4
  • 1 <= nums[i] <= 10^4

Analysis:

In the sequence 1-n, one of the values repeats and one of the values disappears. Find the number that repeats and the number that disappears.

Idea 1:

We’re going through the array, storing all the elements in the map, and after we’ve found the duplicate numbers, we’re going to look for the missing numbers. Simple analysis of the characteristics of sequence, n = 1 + 2 + (n – 1), namely the fore and aft two together, the result is consistent, so at this point we traverse sequence of the first half, with to get the sum of the value minus the traversal determine whether the results in the map, if not can infer the results is the disappearance of Numbers, or continue to traverse.

Idea 2:

The same logic follows the same idea. We iterate through the array and store all the elements in the map. In the process, we have found the repeated numbers, and then we need to find the missing numbers. By simple analysis of the sequence characteristics given, we can know that according to the Gaussian formula n X (n + 1)/2 = sum of correct array, and then iterate over the number group, the sum is gradually subtracted from the traversal value, and the value of sum after the traversal is completed = the number that disappears – the number that repeats. And then you add it to the number that we already know to repeat to get the answer.

Idea 3:

Since the numbers in the sequence are 1-n, we can construct an array of length n + 1 and use the 1-n positions in the array to store the numbers in the sequence. This step replaces the map. The other ideas are basically the same as above.

Problem solving:

1. Think right
> Use HashMap to cache duplicate data. Public static int[] findErrorNum(int[] nums) {HashMap HashMap = new HashMap(); public static int[] findErrorNum(int[] nums) { int repetitiveNum = 0; int missNum = 0; for (int i = 0; i < nums.length; i++) { if (null ! = hashMap.get(nums[i])) { repetitiveNum = nums[i]; } else { hashMap.put(nums[i], nums[i]); } } int index = 1; int sum = nums.length + 1; int middleIndex = (nums.length + 1) / 2; // This could be optimized out of the equation, but it's a good idea. While (index <= middleIndex) {if (hashMap.get(index) == NULL) {missNum = index; break; } if (null == hashMap.get(sum - index)) { missNum = sum - index; break; } index++; } return new int[] {repetitiveNum, missNum}; } ` ` `Copy the code
2. Use HashMap for caching and logical analysis
/** * Observation logic + HashMap */ public static int[] findErrorNum3(int[] nums) {Map  hashMap = new HashMap(); int repetitiveNum = 0; int missNum = 0; int sum = nums.length * (nums.length + 1) / 2; for (int num : nums) { sum -= num; If (null! = null! = null! = null! = null! = hashMap.get(num)) { repetitiveNum = num; } else { hashMap.put(num, num); = repetitiveNum+sum; // Repetition = repetitiveNum+sum; // Repetition = repetitiveNum+sum; return new int[] {repetitiveNum, missNum}; } ` ` `Copy the code
3. Use a Boolean array to store whether the number corresponding to the subscript appears +
> public static int[] findErrorNum4(int[] nums) {int int (int[] nums) {static int[] findErrorNum4(int[] nums) repetitiveNum = 0; int missNum = 0; int sum = nums.length * (nums.length + 1) / 2; Boolean [] appeared = new Boolean [nums.length +1]; for (int num : nums) { sum -= num; if (appeared[num]) { repetitiveNum = num; } appeared[num]= true; } // After subtracting, we get the difference between the repeating numbers and the missing numbers missNum = repetitiveNum+sum; return new int[] {repetitiveNum, missNum}; } ` ` `Copy the code
4. Use normal data types + observation logic
Public static int[] findErrorNum5(int[] nums) {int repetitiveNum = 0; int missNum = 0; int sum = nums.length * (nums.length + 1) / 2; Int [] sortArray = new int[nums.length +1]; int[] sortArray = new int[nums.length +1]; for (int num : nums) { sum -= num; if (sortArray[num] == num) { repetitiveNum = num; } sortArray[num] = num; } // After subtracting, we get the difference between the repeating numbers and the missing numbers missNum = repetitiveNum + sum; return new int[] {repetitiveNum, missNum}; } ` ` `Copy the code