当前位置:网站首页>LeetCode41——First Missing Positive——hashing in place & swap
LeetCode41——First Missing Positive——hashing in place & swap
2022-07-06 09:02:00 【Zheyuan Zou】
This problem lets us find the missing first element in an array , That is to say The smallest positive number , The questions are as follows :
In fact, it is not difficult to realize this function , The difficulty lies in the problem of the algorithm Time and space complexity make constraints at the same time , That is, the complexity of time is O ( n ) O(n) O(n), At the same time, the spatial complexity is O ( 1 ) O(1) O(1).
Before finishing this problem , One very important observation is :
For length is N Array of nums, The minimum missing positive number will only be in the interval [ 1 , N + 1 ] [1, N + 1] [1,N+1] Inside , in other words , The length is N The array of will only occupy [ 1 , N ] [1,N] [1,N] this N A positive integer , So that the first missing positive integer is N+1. Other special cases include the presence of greater than in the array N The positive integer , Or non positive integer (<=0 Number of numbers ), Will make the smallest missing positive integer fall in [ 1 , N ] [1,N] [1,N] In this range , This conclusion is the premise to complete this problem .
Time complexity and space complexity are both O ( n ) O(n) O(n) The algorithm of can be Apply for a length of n Array of Flag Express [ 1 , N ] [1,N] [1,N], For convenience, I take one more element here , Then mark one by one in nums The elements that appear in , Then look at the first positive number that doesn't appear . The code is as follows :
int firstMissingPositive(vector<int>& nums) {
/*O(n)-O(n) algorithm*/
/*apply for a flag array to record existing element*/
bool* Flag = new bool [nums.size() + 1];
for(int i = 0 ; i <= nums.size() ; ++i)
Flag[i] = false;
/*set flag[nums[i]] as true when nums[i]∈[1, N]*/
size_t Size = nums.size();
int Result = Size + 1;
for(int i = 0 ; i < nums.size() ; ++i)
if(nums[i] > 0 && nums[i] <= Size)
Flag[nums[i]] = true;
/*search for the first missing positive number*/
for(int i = 1 ; i <= nums.size() ; ++i)
if(!Flag[i])
{
Result = i;
break;
}
delete [] Flag;
return Result;
}
This simple way increases the spatial complexity , Reduced time complexity , Just traverse 2 The number group is ok . However, it still fails to meet the requirements of the topic while taking into account the time complexity and space complexity , Here you are The two methods To achieve this goal ( Learned from the official explanation , cry :(:
One 、 In place hash (hashing in place)
This way is mainly in the original nums Array [ 1 , N ] [1,N] [1,N] The tag , This algorithm is divided into the following steps :
- Traverse nums for the first time , Will the Less than or equal to 0 All elements of are modified to N+1,N It's array length . This is because Later, you need to subtract... From the elements in the array 1 Mark as a subscript nums The elements in . Negative numbers and 0 subtract 1 Then the index value will become negative . Modified into N+1 Then it will eliminate this problem , and N+1-1 = N, It will not be marked nums Any element in (nums The maximum available index is N-1).
- Traverse nums The second time , take nums Array Between the range [ 1 , N ] [1,N] [1,N] Subtract 1 As a subscript , Set the element corresponding to the subscript to a negative number to indicate that this element exists .
- Traverse nums third time , Look at the first positive integer that appears in nums Which one of them , Let's say the number one in the array is i Bits are positive , that Indicates the positive number corresponding to this index i+1 Never had . Assume negative numbers , So the first positive number that doesn't appear is N+1.
The following is the source code of the implementation :
int firstMissingPositive(vector<int>& nums) {
int Size = nums.size();
/*Iteration 1*/
for(int i = 0 ; i < Size ; ++i)
if(nums[i] <= 0)
nums[i] = Size + 1;
/*Iteration 2*/
for(int i = 0 ; i < Size ; ++i)
{
int num = abs(nums[i]); // num must be larger than 0
if(num <= Size) // make sure the num is less than N
nums[num - 1] = -abs(nums[num - 1]); // make sure the value is negative
}
/*Iteration 3*/
for(int i = 0 ; i < Size ; ++i)
if(nums[i] > 0)
return i + 1;
return Size + 1;
}
Two 、 Local exchange (swap)
This algorithm is simpler than local hash , Its core idea is to put every element into it “ belong ” The location of . say concretely , One is worth x ∈ [ 1 , N ] x \in [1,N] x∈[1,N] The elements of , It should be indexed x-1 The location of , We just need Swap it with the element where it should be that will do .
But note that this exchange is not It was done in one stroke , The newly replaced element also needs to be arranged in the position it should be , So this is a The logic of the cycle . Finally, there is a special case that needs to be discussed , That's it If the two elements exchanged are the same , You're going to fall into a dead circle ( The two elements are constantly changing ), Therefore, the discussion and avoidance of this situation should be added to the conditions of circulation .
One last check nums Array , The first element that appears where it should not appear Is the smallest positive number missing .
The overall code is as follows :
int firstMissingPositive(vector<int>& nums) {
int Size = nums.size();
for(int i = 0 ; i < Size ; ++i)
{
/*2 conditions:*/
/*1.nums[i] ∈ [1,N]*/
/*2.avoid infinite loop*/
while(nums[i] > 0 && nums[i] <= Size && nums[i] != nums[nums[i] - 1])
swap(nums[i], nums[nums[i] - 1]);
}
for(int i = 0 ; i < Size ; ++i)
if(nums[i] != i + 1)
return i + 1;
return Size + 1;
}
边栏推荐
- 多元聚类分析
- Guangzhou will promote the construction of a child friendly city, and will explore the establishment of a safe area 200 meters around the school
- Simclr: comparative learning in NLP
- Esp8266-rtos IOT development
- Unsupported operation exception
- [embedded] print log using JLINK RTT
- What is the role of automated testing frameworks? Shanghai professional third-party software testing company Amway
- Selenium+pytest automated test framework practice
- ant-design的走马灯(Carousel)组件在TS(typescript)环境中调用prev以及next方法
- Using C language to complete a simple calculator (function pointer array and callback function)
猜你喜欢
TP-LINK 企业路由器 PPTP 配置
[oc]- < getting started with UI> -- common controls uibutton
I-BERT
Using pkgbuild:: find in R language_ Rtools check whether rtools is available and use sys The which function checks whether make exists, installs it if not, and binds R and rtools with the writelines
Using C language to complete a simple calculator (function pointer array and callback function)
The ECU of 21 Audi q5l 45tfsi brushes is upgraded to master special adjustment, and the horsepower is safely and stably increased to 305 horsepower
一篇文章带你了解-selenium工作原理详解
MySQL uninstallation and installation methods
Mise en œuvre de la quantification post - formation du bminf
SAP ui5 date type sap ui. model. type. Analysis of the parsing format of date
随机推荐
UnsupportedOperationException异常
Tdengine biweekly selection of community issues | phase III
Export IEEE document format using latex
Using label template to solve the problem of malicious input by users
Notes 01
ant-design的走马灯(Carousel)组件在TS(typescript)环境中调用prev以及next方法
Pytest参数化你不知道的一些使用技巧 /你不知道的pytest
[oc]- < getting started with UI> -- common controls uibutton
[OC foundation framework] - [set array]
I-BERT
Promise 在uniapp的简单使用
UML diagram memory skills
Leetcode: Sword finger offer 48 The longest substring without repeated characters
项目连接数据库遇到的问题及解决
TP-LINK enterprise router PPTP configuration
Different data-driven code executes the same test scenario
KDD 2022 paper collection (under continuous update)
Pytest之收集用例规则与运行指定用例
Leetcode: Jianzhi offer 04 Search in two-dimensional array
LeetCode:剑指 Offer 03. 数组中重复的数字