11package com .cheehwatang .leetcode ;
22
3- /**
4- * Problem:
5- * An array of integers 'nums' with length of 'n', which originally contains all the numbers from 1 to 'n',
6- * but currently contains an error, which resulted in the repetition of one number and loss of another number.
7- * Return an integer array representing:
8- * 1. the number that occurs twice, and
9- * 2. the number that is missing.
10- *
11- *
12- * Example 1:
13- * Input : nums = [1,1]
14- * Output : [1,2]
15- * Explanation: The integer '1' occurs twice, while integer '2' is missing.
16- *
17- *
18- * Example 2:
19- * Input : nums = [3,2,2,4]
20- * Output : [2,1]
21- * Explanation: The 'nums' contains the number from 1 to 4. The integer '2' occurs twice, while integer '1' is missing.
22- *
23- *
24- * @author Chee Hwa Tang
25- */
3+ // Time Complexity : O(n),
4+ // where 'n' is the length of 'nums'.
5+ // Since we know that the sorted array would be from 1 to 'n', the implemented sorting function only has
6+ // time complexity of O(2n), with the sorting and traversal of 'nums' each results in O(n).
7+ // Additionally, we traverse the array once more to find the missing and the duplicate numbers.
8+ //
9+ // Space Complexity : O(1),
10+ // as the auxiliary space used is independent on the size of the input.
2611
2712public class SetMismatch_Sorting {
2813
@@ -44,26 +29,30 @@ public int[] findErrorNums(int[] nums) {
4429 int correct = nums [i ] - 1 ;
4530 // If the integer at 'i' is not at the correct index, we swap nums[i] to its correct position.
4631 // As the number swapped to position 'i' maybe not be correct, continue swapping.
32+ // Note that if we encounter the duplicate, 'nums[i] != nums[correct]' would return false,
33+ // thus continuing to the next number while keeping the duplicate number in the missing position.
4734 if (nums [i ] != nums [correct ]) {
4835 swap (nums , i , correct );
4936 }
5037 else {
5138 i ++;
5239 }
5340 }
54- // Note that result[0] is the duplicate integer, result[1] is the missing integer.
55- int [] result = new int [2 ];
41+ // Optional to use result = new int[], with result[0] == duplicate, and result[1] == missing.
42+ // Here, we use separate variable for readability.
43+ int duplicate = 0 ;
44+ int missing = 0 ;
5645 // Traverse the "sorted" array once more to find the integer that is not in its position.
5746 for (int j = 0 ; j < nums .length ; j ++) {
5847 if (j + 1 != nums [j ]) {
5948 // nums[j] is the duplicate.
60- result [ 0 ] = nums [j ];
49+ duplicate = nums [j ];
6150 // j + 1 is the missing number.
62- result [ 1 ] = j + 1 ;
51+ missing = j + 1 ;
6352 break ;
6453 }
6554 }
66- return result ;
55+ return new int []{ duplicate , missing } ;
6756 }
6857
6958 // Method to swap elements.
0 commit comments