Problem: here
This is a fascinating problem, which has multiple ways to solve
Several approaches
- Sort and find the missing numbers. Simple and easy to implement. O(1) in space and O(n log n) in runtime.
- Using HashSet. Put all the numbers in the array into a set. Go through the numbers from 0 to n, if it is not in the set, return that number. Space and time complexity will both be O(n).
- Using math. We can easily calculate the sum from 0 to n. Then subtract that with the sum of the elements in the array to get the missing number.
- Using some trick of swapping the positions of the elements in the array. (This will be discussed later in this post)
- Bit Manipulation (I am not sure about this yet so I will save that for later)
Swapping elements approach to solve this problem
Some observations that we have are:
- We have a range from 0 to n, which is n + 1 elements. The array only has n positions (indices). So, in order to conduct the in place element swap, we somehow need to reduce the needed space to only support n elements.
- Since the numbers are in range, they will be consecutive, if we sort them, an element with a value i will be in the positions of i - 1 (0-based index).
With these observations, we can remove element 0 from considering for place elements swaps:
- We just need to make sure there is already a 0 in the arrays
- since if swap 0, we will need index -1, which is not supported (or not good to be used)
- Here is a simple explanation of the process:
/**
- swap the positions of the element in place? => will be missing 1 spot
-> How about we ignore the number 0?
for each element in the array:
- if element == index + 1: Continue
- if element == 0: ignore
- else, conduct swap
at index i, we have value val.
swap numbers[i] with numbers[val - 1].
Then continue to swap numbers[i] until it matches the value
- in the end, go through and check if there is any missing element in the array
*/
class Solution {
int[] nums;
public void swap(int idx) {
int val = nums[idx];
if (val == idx + 1) return;
else if (val == 0) return;
else {
int temp = nums[val - 1];
nums[val - 1] = val;
nums[idx] = temp;
swap(idx);
}
}
public int missingNumber(int[] nums) {
this.nums = nums;
boolean hasZero = false;
for (int n: nums) {
if (n == 0) {
hasZero = true;
break;
}
}
if (!hasZero) {
return 0;
}
for (int i = 0; i < nums.length; i++) {
if (nums[i] == i + 1) {
continue;
} else {
swap(i);
}
}
// System.out.println(Arrays.toString(this.nums));
int result = -1;
for (int i = 0; i < nums.length; i++) {
if (nums[i] != i + 1) {
result = i + 1;
break;
}
}
return result;
}
}
Top comments (0)