This is the fourth day of my participation in the August More text Challenge. For details, see: August More Text Challenge
preface
About the LeetCode array type problem related solutions, it can be seen that LeetCode array type problem before doing must see, classification solution summarized the problem, can be used to improve a single. If you think it is helpful, remember to give more likes and attention, thank you!
Topic describes
Given an unsorted array of integers, nums, ask you to find the smallest positive integer that is not present in it.
Implement a solution of O(n) time complexity that uses only constant levels of extra space.
Example 1: Input: nums = [1,2,0] Output: 3
Example 2: input: nums = [3,4,-1,1] output: 2
Example 3: input: nums = [7,8,9,11,12] output: 1
Link: leetcode-cn.com/problems/fi…
Answer key
- Start with a simple solution. You can think of using the hash method, the element in numS as the hash index, the element in numS, the corresponding hash index is 1. We can start at position 1 to check whether the hash is 1. Once we find that the hash is not present or we have traversed to the end of the hash array, we can find the corresponding value. The specific code is shown below. Although the time complexity of this method is O(n), the space complexity is O(Max (nums)), so it does not meet the requirements of the problem.
/ * * *@param {number[]} nums
* @return {number}* /
var firstMissingPositive = function (nums) {
let hash = [];
for (let n of nums) {
if (n >= 0) {
hash[n] = 1; }}let res = 1;
let i = 1;
while (i < hash.length) {
if(! hash[i]) { res = i;break;
}
i++;
}
if (i === hash.length) {
res = hash.length;
}
return res;
};
Copy the code- In method 1, we use the hash method to achieve the time complexity of O(n), but the space complexity is not constant, is there a better way to reduce the space complexity? You’re probably smart enough to realize that we can reuse the nums array without having to create a new hash array, so how do we do that? The first thing we need to make sure is that the final positive integer to be returned must be in the range of [1, n+1], where n is the length of nums. And once we’ve got that, we can do it, but we just have to put each element in its corresponding position, and then check from the beginning to see if the subscripts correspond to the elements at each position. In particular, if I have element 1, I put 1 at 0, and element 5 at 4, that means I plus one, so if I don’t have an element at I + 1, I + 1 is the answer, If all the elements are corresponding, return n + 1. In the adjustment process we may encounter numbers that are less than 1 or greater than n, so just skip this position. See the code below for specific methods. We can call this method in place hash with time complexity O(n) and space complexity O(1).
/ * * *@param {number[]} nums
* @return {number}* /
var firstMissingPositive = function(nums) {
const len = nums.length
const swap = (a, b) = > {
let tmp = nums[a]
nums[a] = nums[b]
nums[b] = tmp
}
for (let i = 0; i < len; ++i) {
// Adjust the element at the I position until it meets the requirement or is out of range
while (nums[i] > 0 && nums[i] < len + 1 && nums[nums[i] - 1] !== nums[i]) {
swap(i, nums[i] - 1)}}for (let i = 0; i < len; ++i) {
if(nums[i] ! == i +1) {
return i + 1}}return len + 1
};
Copy the code