给定一个包含正负元素的未排序数组。使用恒定的额外空间，在O（n）时间内查找数组中缺少的最小正数。允许修改原始数组。 例如：
null
Input: {2, 3, 7, 6, 8, -1, -10, 15}Output: 1Input: { 2, 3, -7, 6, 8, 1, -10, 15 }Output: 4Input: {1, 1, 0, -1, -2}Output: 2
我们已经讨论了O（n）时间和O（1）额外空间解 以前的 邮递在这篇文章中，我们将讨论另一种解决方案。 我们使与给定数组元素对应的索引处的值等于一个数组元素。例如：考虑数组= { 2, 3, 7，6, 8，- 1，-10, 15 }。为了标记这个数组中元素2的存在，我们将arr[2-1]=2。在数组下标[2-1]中，2是要标记的元素，1被减去，因为我们在索引值范围[0，N-1]上映射元素值范围[1，N]。但是如果我们使arr[1]=2，我们将丢失存储在arr[1]的数据。为了避免这种情况，我们首先存储arr[1]中的值，然后更新它。接下来，我们将标记之前存在于arr[1]的元素的存在，即3。显然，这会导致对数组进行某种类型的随机遍历。现在我们必须指定一个条件来标记遍历的结束。有三个条件标志着此遍历的结束： 1.如果要标记的元素为负：无需标记该元素的存在，因为我们感兴趣的是找到第一个缺失的正整数。因此，如果发现一个负元素，只需结束遍历，因为不再标记元素的存在。 2.如果要标记的元素大于N：无需标记此元素的存在，因为如果此元素存在，则它肯定已取代大小为N的数组中[1，N]范围内的元素，从而确保我们的答案位于[1，N]范围内。因此，只需结束遍历，不再标记元素的存在。 3.如果已经标记了当前元素的存在：假设要标记为存在的元素是val。如果arr[val-1]=val，那么我们已经标记了该元素的存在。因此，只需结束遍历，不再标记元素的存在。 还要注意的是，在[1，N]范围内的数组的所有元素可能都没有标记为当前遍历中存在。为了确保该范围内的所有元素都标记为存在，我们检查位于该范围内的数组的每个元素。如果元素没有标记，那么我们将从该数组元素开始新的遍历。 在我们标记了[1，N]范围内所有数组元素的存在之后，我们检查哪个索引值ind不等于ind+1。如果arr[ind]不等于ind+1，则ind+1是最小的正缺失数。回想一下，我们正在将索引值范围[0，N-1]映射到元素值范围[1，N]，因此1被添加到ind。如果没有找到这样的ind，那么范围[1，N]中的所有元素都存在于数组中。所以第一个缺失的正数是N+1。 这个解决方案在O（n）时间内是如何工作的？ 请注意，在最坏的情况下，范围[1，N]中的每个元素最多遍历两次。首先，从范围中的其他元素开始执行遍历。第二，检查是否需要从此元素启动新的遍历，以标记未标记元素的存在。在最坏的情况下，[1，N]范围内的每个元素都存在于数组中，因此所有N个元素都被遍历两次。总的计算量是2*n，因此时间复杂度是O（n）。 以下是上述方法的实施情况：
C++
/* CPP program to find the smallest positive missing number */ #include <bits/stdc++.h> using namespace std; // Function to find smallest positive // missing number. int findMissingNo( int arr[], int n) { // to store current array element int val; // to store next array element in // current traversal int nextval; for ( int i = 0; i < n; i++) { // if value is negative or greater // than array size, then it cannot // be marked in array. So move to // next element. if (arr[i] <= 0 || arr[i] > n) continue ; val = arr[i]; // traverse the array until we // reach at an element which // is already marked or which // could not be marked. while (arr[val - 1] != val) { nextval = arr[val - 1]; arr[val - 1] = val; val = nextval; if (val <= 0 || val > n) break ; } } // find first array index which is // not marked which is also the // smallest positive missing // number. for ( int i = 0; i < n; i++) { if (arr[i] != i + 1) { return i + 1; } } // if all indices are marked, then // smallest missing positive // number is array_size + 1. return n + 1; } // Driver code int main() { int arr[] = { 2, 3, 7, 6, 8, -1, -10, 15 }; int arr_size = sizeof (arr) / sizeof (arr[0]); int missing = findMissingNo(arr, arr_size); cout << "The smallest positive missing number is " << missing; return 0; } |
JAVA
/* Java program to find the smallest positive missing number */ import java.io.*; class GFG { // Function to find smallest positive // missing number. static int findMissingNo( int []arr, int n) { // to store current array element int val; // to store next array element in // current traversal int nextval; for ( int i = 0 ; i < n; i++) { // if value is negative or greater // than array size, then it cannot // be marked in array. So move to // next element. if (arr[i] <= 0 || arr[i] > n) continue ; val = arr[i]; // traverse the array until we // reach at an element which // is already marked or which // could not be marked. while (arr[val - 1 ] != val) { nextval = arr[val - 1 ]; arr[val - 1 ] = val; val = nextval; if (val <= 0 || val > n) break ; } } // find first array index which is // not marked which is also the // smallest positive missing // number. for ( int i = 0 ; i < n; i++) { if (arr[i] != i + 1 ) { return i + 1 ; } } // if all indices are marked, then // smallest missing positive // number is array_size + 1. return n + 1 ; } // Driver code public static void main (String[] args) { int arr[] = { 2 , 3 , 7 , 6 , 8 , - 1 , - 10 , 15 }; int arr_size = arr.length; int missing = findMissingNo(arr, arr_size); System.out.println( "The smallest positive" + " missing number is " + missing); } } // This code is contributed by anuj_67. |
Python 3
# Python 3 program to find the smallest # positive missing number # Function to find smallest positive # missing number. def findMissingNo(arr, n): # to store current array element # to store next array element in # current traversal for i in range (n) : # if value is negative or greater # than array size, then it cannot # be marked in array. So move to # next element. if (arr[i] < = 0 or arr[i] > n): continue val = arr[i] # traverse the array until we # reach at an element which # is already marked or which # could not be marked. while (arr[val - 1 ] ! = val): nextval = arr[val - 1 ] arr[val - 1 ] = val val = nextval if (val < = 0 or val > n): break # find first array index which is # not marked which is also the # smallest positive missing # number. for i in range (n): if (arr[i] ! = i + 1 ) : return i + 1 # if all indices are marked, then # smallest missing positive # number is array_size + 1. return n + 1 # Driver code if __name__ = = "__main__" : arr = [ 2 , 3 , 7 , 6 , 8 , - 1 , - 10 , 15 ] arr_size = len (arr) missing = findMissingNo(arr, arr_size) print ( "The smallest positive" , "missing number is " , missing) # This code is contributed # by ChitraNayal |
C#
/* C# program to find the smallest positive missing number */ using System; class GFG { // Function to find smallest // positive missing number. static int findMissingNo( int []arr, int n) { // to store current // array element int val; // to store next array element // in current traversal int nextval; for ( int i = 0; i < n; i++) { // if value is negative or greater // than array size, then it cannot // be marked in array. So move to // next element. if (arr[i] <= 0 || arr[i] > n) continue ; val = arr[i]; // traverse the array until we // reach at an element which // is already marked or which // could not be marked. while (arr[val - 1] != val) { nextval = arr[val - 1]; arr[val - 1] = val; val = nextval; if (val <= 0 || val > n) break ; } } // find first array index which // is not marked which is also // the smallest positive missing // number. for ( int i = 0; i < n; i++) { if (arr[i] != i + 1) { return i + 1; } } // if all indices are marked, // then smallest missing // positive number is // array_size + 1. return n + 1; } // Driver code public static void Main (String[] args) { int []arr = {2, 3, 7, 6, 8, -1, -10, 15}; int arr_size = arr.Length; int missing = findMissingNo(arr, arr_size); Console.Write( "The smallest positive" + " missing number is " + missing); } } // This code is contributed // by shiv_bhakt. |
PHP
<?php // PHP program to find // the smallest positive // missing number // Function to find smallest // positive missing number. function findMissingNo( $arr , $n ) { // to store current // array element $val ; // to store next array element // in current traversal $nextval ; for ( $i = 0; $i < $n ; $i ++) { // if value is negative or // greater than array size, // then it cannot be marked // in array. So move to // next element. if ( $arr [ $i ] <= 0 || $arr [ $i ] > $n ) continue ; $val = $arr [ $i ]; // traverse the array until // we reach at an element // which is already marked // or which could not be marked. while ( $arr [ $val - 1] != $val ) { $nextval = $arr [ $val - 1]; $arr [ $val - 1] = $val ; $val = $nextval ; if ( $val <= 0 || $val > $n ) break ; } } // find first array index // which is not marked // which is also the smallest // positive missing number. for ( $i = 0; $i < $n ; $i ++) { if ( $arr [ $i ] != $i + 1) { return $i + 1; } } // if all indices are marked, // then smallest missing // positive number is // array_size + 1. return $n + 1; } // Driver code $arr = array (2, 3, 7, 6, 8, -1, -10, 15); $arr_size = sizeof( $arr ) / sizeof( $arr [0]); $missing = findMissingNo( $arr , $arr_size ); echo "The smallest positive " . "missing number is " , $missing ; // This code is contributed // by shiv_bhakt. ?> |
Javascript
<script> /* Javascript program to find the smallest positive missing number */ // Function to find smallest positive // missing number. function findMissingNo(arr, n) { // to store current array element var val; // to store next array element in // current traversal var nextval; for ( var i = 0; i < n; i++) { // if value is negative or greater // than array size, then it cannot // be marked in array. So move to // next element. if (arr[i] <= 0 || arr[i] > n) continue ; val = arr[i]; // traverse the array until we // reach at an element which // is already marked or which // could not be marked. while (arr[val - 1] != val) { nextval = arr[val - 1]; arr[val - 1] = val; val = nextval; if (val <= 0 || val > n) break ; } } // find first array index which is // not marked which is also the // smallest positive missing // number. for ( var i = 0; i < n; i++) { if (arr[i] != i + 1) { return i + 1; } } // if all indices are marked, then // smallest missing positive // number is array_size + 1. return n + 1; } // Driver code var arr = [ 2, 3, 7, 6, 8, -1, -10, 15 ]; var arr_size = arr.length; var missing = findMissingNo(arr, arr_size); document.write( "The smallest positive missing number is " + missing); </script> |
输出：
The smallest positive missing number is 1
时间复杂性： O（n） 辅助空间： O（1）
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
