Topic Description (Difficult Difficulty)
Given a list of numbers, find the smallest positive number missing. It limits the time complexity to O (n) and space complexity to O (1).
Solution one, interchange
See here.
If we don’t limit space complexity, we can think of it this way. Store the numbers sequentially in an equally large array.
For example, the array nums [3, 4-1, 1, 8] has a size of 5. Then create an array of equal size a, initialized to [-1, -1, -1, -1, -1]. We then iterate over nums, storing the numbers in their respective locations. 1 is stored in the first position of array A (a [0]), 2 is stored in the second position of array A (a [1]), 3 is stored in the third position of array A (a [2])…
Nums [0] = 3, update a [-1, -1, 3, -1, -1].
Nums [1] = 4, update a [-1, -1, 3, 4, -1].
Nums [2] = -1, not positive, ignored.
Nums [3] equals 1, update a [1, -1, 3, 4, -1].
Nums [4] is equal to 8, and our ARRAY a can only store 1 through 5, so we ignore it again.
Finally, we just need to traverse the array of A, encountering the first a [I]! Equals I plus 1, that means I plus 1 is missing. Because every place in our array a has a number 1 higher than the index.
Of course, this is all based on having an extra space. What if I don’t have extra space?
Let’s just use the original array as an A array. The problem with that is that the previous number gets overwritten. Before we overwrite, we put it back where the current number is, in other words, we switch places. And then you swap the number back to where it should be, and then you swap the number back until it’s less than zero, or bigger than the size of the array, or it’s the number you put in the current position. It then iterates over the next nums number. Let’s see.
nums = [ 3 4 -1 1 8 ]
Update nums [-1, 4, 3, 1, 8] with nums [0] equal to 3, put 3 in the third position and put -1 back in the previous third position.
Nums [0] = -1, not a positive number, ignored.
Update nums [-1, 1, 3, 4, 8] with nums [1] equal to 4, put 4 in the fourth position and put 1 back in the previous fourth position.
Nums [1] = 1, put the 1 in the first position, and put the -1 in the first position before, update nums [1, -1, 3, 4, 8].
Nums [1] = -1, not a positive number, ignored.
Nums [2] is equal to 3, just in the third position, never mind.
Nums [3] is equal to 4, which happens to be in the fourth position, never mind.
Nums [4] is equal to 8, and our nums array can only store 1 through 5, so we ignore it again.
Finally, we just need to traverse the NUMS array and encounter the first NUMS [I]! Equals I plus 1, that means I plus 1 is missing. Because our NUMS array holds a number one higher than the subscript at every position.
If you look at the code, it’s a for loop with a while loop inside it.
public int firstMissingPositive(int[] nums) {
int n = nums.length;
// Iterate over each number
for (int i = 0; i < n; i++) {
// Determine the number swapped back
while (nums[i] > 0&& nums[i] <= n && nums[i] ! = nums[nums[i] -1]) {
// the nums[I] subscript is nums[I] -1
swap(nums, i, nums[i] - 1); }}// find the first nums[I]! = I + 1
for (int i = 0; i < n; i++) {
if(nums[i] ! = i +1) {
return i + 1; }}// Return n + 1 if all the previous numbers are satisfied
return n + 1;
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
Copy the codeTime complexity: The for loop has a while loop inside it. Roughly speaking, the time complexity is O (n²). Let’s look at the logic of the algorithm. Because every time we swap, we put a number where it should be, and there are only n numbers, so the swap function in the while, at most, does n times. So the time complexity is, more precisely, order n.
Space complexity: O (1).
Solution two notation
See here.
Again, let’s think about what we could do if we had extra space.
Again, for nums = [3, 4-1, 1, 8], we create an equally large array a, initialized to [false, false, false, false, false]. And then if there’s a 1 in nums, change the first position, a [0], to true. If nums contains m, change a [m-1] to true. Let’s look at a specific example.
nums = [ 3 4 -1 1 8]
Nums [0] = 3, update a [false, false, true, false, false].
Nums [1] = 4, update a [false, false, true, true, false].
Nums [2] = -1, not positive, ignored.
Nums [3] = 1, update a [true, false, true, true, false].
Nums [4] is equal to 8, and our ARRAY a can only store 1 through 5, so we ignore it again.
Then iterate over the set A, if a [I]! = true. So, we return I plus 1. Because a [I] = true means that I + 1 exists.
Again, we don’t have any extra space, we have to use the original array nums.
Again, we use nums directly as the array A.
But when we update, if we just set the number of the array to true, then the original number is gone. There’s a neat trick here.
Given that all we really care about is the positive numbers. Initially the array a is initialized to false, so we treat positive numbers as false and negative numbers as true. If we want to assign nums [I] to true, if nums [I] is a positive number, we simply take the negative number as the marker. If nums [I] is negative, we don’t care. And the nice thing about this is, when we go through the numbers, we just take the absolute value, which is the original number.
And of course that raises the question, if we take the absolute value, what do we do with the previous negative number? When you take the absolute value, you get interference. Just to be blunt, let’s put all the positive numbers out front, let’s just think about the positive numbers. Negative numbers and zeros go to the end, and you don’t have to iterate.
Let’s look at a specific example.
nums = [ 3 4 -1 1 8]
Let’s put all the positive numbers first, and only consider the positive numbers. Nums = [3, 4, 1, 8], positive numbers as false, negative numbers as true. So nums can be viewed as [false, false, false, false].
Nums [0] = 3, nums [3, 4, -1, 8]; update nums [3, false, true, false].
Nums [1] = 4, make the fourth digit negative, update nums [3, 4, -1, -8], as [false, false, true, true].
Nums [2] = -1, take absolute value of 1, make the first digit negative, update nums [-3, 4, -1, -8], can be seen as [true, false, true].
Nums [3] is equal to -8, take the absolute value of 8, our nums array only considers 1 to 4, so ignore.
If nums [I] is greater than 0, then I + 1 is missing. Because positive numbers mean false.
I’ve moved the positive numbers to the front, and I’ve written two algorithms, and I’ve commented them in the code, so you can look at them.
public int firstMissingPositive(int[] nums) {
int n = nums.length;
// Move the positive number to the front and get the number of positive numbers
int k = positiveNumber(nums);
for (int i = 0; i < k; i++) {
// Get the index to mark
int index = Math.abs(nums[i]) - 1;
if (index < k) {
// Check if the number of positions to be marked is less than 0
int temp = Math.abs(nums[index]);
nums[index] = temp < 0? temp : -temp; }}// find the first position greater than 0
for (int i = 0; i < k; i++) {
if (nums[i] > 0) {
return i + 1; }}return k + 1;
}
private int positiveNumber(int[] nums) {
// The first solution is to swap all the negative numbers and 0 to the end
/* int n = nums.length; for (int i = 0; i < n; i++) { while (nums[i] <= 0) { swap(nums, i, n - 1); n--; if (i == n) { break; } } } return n; * /
// Use a pointer to p to ensure that everything before p is positive. Iterating through NUMs, each time a positive number is encountered, it is swapped to the position of the p pointer, and the P pointer moves backwards
int n = nums.length;
int p = 0;
for (int i = 0; i < n; i++) {
if (nums[i] > 0) { swap(nums, i, p); p++; }}return p;
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
Copy the codeTime complexity: O (n).
Space complexity: O (1).
The total
So for this kind of space complexity, we can think about what we can do if we have an equal space. And then we’ll think about what we can do with the original array, just to make sure that the information in the array is not lost. Now, there are two main methods that we’ve encountered so far: swapping and taking negatives.
See Leetcode.Wang for more details on popular problems.