資料結構
網路
關係資料庫管理系統 (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+ 次瀏覽
