数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
服装学
法学查找无序数组中缺失的最小正数
我们的目标是从无序数组中找到缺失的最小正数。我们将得到一个包含正数和负数的数组a[]，在这个问题中，我们需要找到该无序数组中缺失的最小正数。我们可以修改给定的数组来解决这个问题。
例如：
输入：a[] = {5, 8, -13, 0, 18, 1, 3}
输出 : 2
输入：a[] = {7, 10, -8, 1, 4}
输出 : 2
在上面的例子中，我们得到一个无序数组作为输入。数组中缺失的最小正整数是我们的输出。
朴素方法
解决这个问题的朴素方法是从1开始搜索给定数组a[]中的所有正数。但这种方法效率不高，因为在最坏的情况下，我们最多可能需要搜索n+1次，这将需要n次迭代。
这种方法的时间复杂度在最坏情况下为O(N^2)，空间复杂度为O(1)，因为不需要额外的空间。
方法
方法一（标记元素）
在这种方法中，我们将通过标记数组中存在的元素来找到无序数组中缺失的最小正数。
这种方法背后的逻辑是在另一个数组中标记给定数组中存在的元素。然后遍历标记元素的数组，并返回第一个未标记的元素。如果所有元素都被标记，则返回（数组大小）+ 1。
以下是上述方法的分步说明：
我们将初始化一个函数来获取数组中缺失的最小正数。
如果给定数组的大小为n，则初始化一个大小为n+1的新数组来标记元素的存在。
我们将把新数组的布尔数据类型在每个索引处初始化为false。
现在遍历原始给定数组，我们将检查第i个数是否为正数且小于或等于n（数组的大小）。如果是，则将新数组的第i个数的索引值更改为true。
在此之后，只需从1开始遍历更新后的标记元素的新数组，并返回我们第一次遇到false的(索引值+1)，这将是数组中缺失的最小正数。
如果我们在遍历标记元素的数组时没有遇到任何false，则返回n+1，其中n是给定无序数组的大小。
示例
以下是上述方法在C++中的实现：
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
//function to find the smallest positive number from the unsorted array
int positiveMissingElement(int a[],int N){
bool isPresent[N+1]={false}; //to mark the presence of elements which are in the given array
for(int i=0;i<N;i++) //iterating over the given array to mark the presence of elements
{
if(a[i]>0 && a[i]<=N) //to check if number is a positive number and to check if it is less than or equal to n
{
isPresent[a[i]]=true;
}
}
for(int i=1;i<=N;i++) //to find the first index which is false as it will be the number which is missing in the original array
{
if(isPresent[i]==false){
return i;
}
}
return N+1;
}
//Driver Code
int main(){
int a[]={ 0, 10, 4, -1, -18 ,1,2};
int S = sizeof(a) / sizeof(a[0]);
int ans=positiveMissingElement(a,S);
cout<<"Missing Positive Element : "<<ans<<endl;
return 0;
}
输出
Missing Positive Element : 3
时间复杂度：O(N)，因为我们只进行了两次n次遍历。
空间复杂度：O(N)，因为我们创建了一个大小为n+1的数组。
方法二（更改输入数组）
在这种方法中，我们将通过执行某些条件操作来更改输入数组以获得所需答案。基本上，我们将首先标记给定数组中存在的、大于n（给定数组的大小）且小于1的所有元素为1。我们将这样做是因为答案总是在[1,n+1]之间。
以下是我们需要遵循的步骤：
由于1是可能从给定数组中缺失的最小正整数。因此，我们将首先遍历给定数组以查看是否存在1。因为它是输入数组中缺失的最小正数，所以如果它不存在，我们将返回1。
如果存在，则重复输入数组的遍历。再次遍历数组时，将每个小于1或大于n的整数都设为1，因为最大的可能答案可以是n+1，其中n是输入数组的大小。
在此之后，再次遍历数组。这一次，对于每个第i个数，我们将通过添加n（数组的大小）来更新a[(a[i]-1)%n]的值。我们取模n是因为在某些情况下，索引的值可能会大于数组的大小。
值小于N的第一个索引，我们将在这个索引值中加1并将其返回，因为这将是我们所需的结果。
示例
以下是上述方法在C++中的实现：
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
//function to find the minimum positive number missing from an array
int positiveMissingElement(int a[],int N){
bool onePresent=false;
for(int i=0;i<N;i++) //to check if 1 is there in the array
{
if(a[i]==1){
onePresent=true;
break;
}
}
if(onePresent==false) //if 1 is missing then return 1
{
return 1;
}
for(int i=0;i<N;i++) //to mark all the elements greater than N and less than 1 as 1
{
if(a[i]<=0||a[i]>=N){
a[i]=1;
}
}
for(int i=0;i<N;i++) //to update the values of indices according to the number present in the array
{
int temp=(a[i]-1)%N;
a[temp]=a[temp]+N;
}
for(int i=0;i<N;i++) //to find the index with value less than or equal to N
{
if(a[i]<=N){
return i+1;
}
}
return N+1;
}
int main(){
int a[]={ 0, 10,3, -12, -2 ,1,2,5,6,4,8};
int S = sizeof(a) / sizeof(a[0]);
int ans=positiveMissingElement(a,S);
cout<<"Missing Positive Element : "<<ans<<endl;
return 0;
}
输出
Missing Positive Element : 7
时间复杂度：O(N)，因为我们只是遍历输入数组。
空间复杂度：O(1)，因为我们没有使用额外的空间。
方法三（使用交换）
在这种方法中，我们将使用交换来获得我们的输出。交换是c++中的一个标准库，用于根据数组中元素的位置交换数组中的两个元素。我们也在这里用到了一些上述方法的概念。
由于答案在1和n+1之间，因此对于大于或等于1且小于或等于n的每个元素，我们将检查它是否在适当的索引上，即a[i]是否等于a[a[i]-1]。如果不是，我们将交换这两个元素。
现在我们将遍历输入数组并检查每个索引处的元素是否等于1 + 索引值。如果不是，则返回i+1。
如果数组中所有元素都等于（索引值+1），则返回n+1。
示例
以下是上述方法在C++中的实现：
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
//function to find minimum positive number missing from the array
int positiveMissingElement(int a[],int N){
for(int i=0;i<N;i++){
while(a[i]>0 && a[i]<=N && a[i]!=a[a[i]-1]){ //for every element to be at right index
swap(a[i],a[a[i]-1]);
}
}
for(int i=0;i<N;i++) //for checking every element and their indices
{
if(a[i]!=i+1) //if not equal then return 1+index value
{
return i+1;
}
}
return N+1; //return n+1 if every element is at right index
}
int main(){
int a[]={10,3,-5,1,5,-20,2,7,4};
int S = sizeof(a) / sizeof(a[0]);
int ans=positiveMissingElement(a,S);
cout<<"Missing Positive Element : "<<ans<<endl;
return 0;
}
输出
Missing Positive Element : 6
时间复杂度：O(N)，因为我们只遍历输入数组两次。
空间复杂度：O(1)，因为我们没有使用任何额外的空间。
方法四（使用排序）
在这种方法中，我们将使用C++中存在的STL库，即sort，用于将数组按升序排序。这种方法的基本思想是我们将对数组进行排序，然后检查是否存在最小正数，即1。如果存在，则将其加1，然后再次检查，直到遍历整个数组。以下是我们将在这种方法中遵循的步骤：
首先，我们将对数组进行排序。
现在声明一个名为temp的变量，并在其中存储1，这是可能从数组中缺失的最小正数。
现在我们将从0开始遍历数组，并在每个索引处检查值是否等于1。
如果该值等于temp，则我们将temp加1，然后再次检查在任何索引处该值是否等于temp，直到数组的大小，即n。
遍历给定数组一次后，缺失的最小数将是存储在变量temp中的数。
返回temp，这将是我们所需的结果。
示例
以下是上述方法在C++中的实现：
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
//function to find the smallest positive number missing from an array
int positiveMissingElement(int a[],int N){
sort(a,a+N); //using sort STL to sort the array
int temp=1; //to check if the number is present in the array
for(int i=0;i<N;i++){
if(a[i]==temp) { //if element is present in the array increase temp by 1
temp++;
}
}
return temp;
}
//Driver Code
int main(){
int a[]={ 0,2,10,3,-10,-20,1,6,4};
int S = sizeof(a) / sizeof(a[0]);
int ans=positiveMissingElement(a,S);
cout<<"Missing Positive Element : "<<ans<<endl;
return 0;
}
输出
Missing Positive Element : 5
时间复杂度：O(N*logN)，因为这是排序函数的时间复杂度。
空间复杂度：O(1)，因为我们没有使用任何额外的空间。
结论
在这篇文章中，我们学习了使用不同的方法来解决查找无序数组中缺失的最小正数的问题。我们使用了四种不同的方法来解决上述问题。
我希望您发现这篇文章有助于解决您关于这个问题的所有疑问。
2K+ 次浏览
