本文概述

• C ++
• C
• Java
• python
• C#
• C ++
• Java
• Python 3
• C#
• 的PHP

你将获得一个包含正负元素的未排序数组。你必须使用恒定的额外空间在O(n)时间内找到数组中最小的正数。你可以修改原始数组。
例子

Input:{2, 3, 7, 6, 8, -1, -10, 15} Output: 1 Input:{ 2, 3, -7, 6, 8, 1, -10, 15 } Output: 4 Input: {1, 1, 0, -1, -2} Output: 2

一种天真的方法解决此问题的方法是搜索给定数组中从1开始的所有正整数。我们可能必须在给定数组中搜索最多n + 1个数字。因此, 在最坏的情况下, 此解决方案需要O(n ^ 2)。
我们可以使用排序以更少的时间来解决它。我们可以在O(nLogn)时间对数组进行排序。数组排序后, 我们要做的就是对数组进行线性扫描。因此, 此方法需要O(nLogn + n)时间, 即O(nLogn)。
我们也可以使用哈希。我们可以建立给定数组中所有正元素的哈希表。一旦建立哈希表。我们可以在哈希表中查找从1开始的所有正整数。一旦我们发现哈希表中不存在的数字, 就将其返回。这种方法平均可能需要O(n)时间, 但需要O(n)额外空间。
O(n)时间和O(1)额外空间解决方案：
这个想法类似于
这个
发布。我们使用数组元素作为索引。
为了标记元素x的存在, 我们将索引x的值更改为负
。但是, 如果存在非正数(-ve和0), 则此方法无效。因此, 我们首先将正数与负数分开, 然后应用该方法。
以下是两步算法。
1)将正数与其他数字分开, 即, 将所有非正数移到左侧。在下面的代码中, segregate()函数完成了这一部分。
2)现在我们可以忽略非正元素, 而只考虑包含所有正元素的数组部分。我们遍历包含所有正数的数组, 并标记元素x的存在, 我们将索引x处的值符号更改为负数。我们再次遍历数组,
打印第一个具有正值的索引
。在下面的代码中, findMissingPositive()函数完成了这一部分。请注意, 在findMissingPositive中, 我们从值中减去了1, 因为C中的索引从0开始。
C ++

/* C++ program to find the smallest positive missing number */ #include < bits/stdc++.h> using namespace std; /* Utility to swap to integers */ void swap( int * a, int * b) { int temp; temp = *a; *a = *b; *b = temp; }/* Utility function that puts all non-positive (0 and negative) numbers on left side of arr[] and return count of such numbers */ int segregate( int arr[], int size) { int j = 0, i; for (i = 0; i < size; i++) { if (arr[i] < = 0) { swap(& arr[i], & arr[j]); j++; //increment count of non-positive integers } }return j; }/* Find the smallest positive missing number in an array that contains all positive integers */ int findMissingPositive( int arr[], int size) { int i; //Mark arr[i] as visited by making arr[arr[i] - 1] negative. //Note that 1 is subtracted because index start //from 0 and positive numbers start from 1 for (i = 0; i < size; i++) { if ( abs (arr[i]) - 1 < size & & arr[ abs (arr[i]) - 1]> 0) arr[ abs (arr[i]) - 1] = -arr[ abs (arr[i]) - 1]; }//Return the first index value at which is positive for (i = 0; i < size; i++) if (arr[i]> 0) //1 is added because indexes start from 0 return i + 1; return size + 1; }/* Find the smallest positive missing number in an array that contains both positive and negative integers */ int findMissing( int arr[], int size) { //First separate positive and negative numbers int shift = segregate(arr, size); //Shift the array and call findMissingPositive for //positive part return findMissingPositive(arr + shift, size - shift); }//Driver code int main() { int arr[] = { 0, 10, 2, -10, -20 }; int arr_size = sizeof (arr) /sizeof (arr[0]); int missing = findMissing(arr, arr_size); cout < < "The smallest positive missing number is " < < missing; return 0; }//This is code is contributed by rathbhupendra

C

/* C program to find the smallest positive missing number */ #include < stdio.h> #include < stdlib.h> /* Utility to swap to integers */ void swap( int * a, int * b) { int temp; temp = *a; *a = *b; *b = temp; }/* Utility function that puts all non-positive (0 and negative) numbers on left side of arr[] and return count of such numbers */ int segregate( int arr[], int size) { int j = 0, i; for (i = 0; i < size; i++) { if (arr[i] < = 0) { swap(& arr[i], & arr[j]); j++; //increment count of non-positive integers } }return j; }/* Find the smallest positive missing number in an array that contains all positive integers */ int findMissingPositive( int arr[], int size) { int i; //Mark arr[i] as visited by making arr[arr[i] - 1] negative. //Note that 1 is subtracted because index start //from 0 and positive numbers start from 1 for (i = 0; i < size; i++) { if ( abs (arr[i]) - 1 < size & & arr[ abs (arr[i]) - 1]> 0) arr[ abs (arr[i]) - 1] = -arr[ abs (arr[i]) - 1]; }//Return the first index value at which is positive for (i = 0; i < size; i++) if (arr[i]> 0) //1 is added because indexes start from 0 return i + 1; return size + 1; }/* Find the smallest positive missing number in an array that contains both positive and negative integers */ int findMissing( int arr[], int size) { //First separate positive and negative numbers int shift = segregate(arr, size); //Shift the array and call findMissingPositive for //positive part return findMissingPositive(arr + shift, size - shift); }int main() { int arr[] = { 0, 10, 2, -10, -20 }; int arr_size = sizeof (arr) /sizeof (arr[0]); int missing = findMissing(arr, arr_size); printf ( "The smallest positive missing number is %d " , missing); getchar (); return 0; }

Java

//Java program to find the smallest //positive missing number import java.util.*; class Main {/* Utility function that puts all non-positive (0 and negative) numbers on left side of arr[] and return count of such numbers */ static int segregate( int arr[], int size) { int j = 0 , i; for (i = 0 ; i < size; i++) { if (arr[i] < = 0 ) { int temp; temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; //increment count of non-positive //integers j++; } }return j; }/* Find the smallest positive missing number in an array that contains all positive integers */ static int findMissingPositive( int arr[], int size) { int i; //Mark arr[i] as visited by making //arr[arr[i] - 1] negative. Note that //1 is subtracted because index start //from 0 and positive numbers start from 1 for (i = 0 ; i < size; i++) { int x = Math.abs(arr[i]); if (x - 1 < size & & arr[x - 1 ]> 0 ) arr[x - 1 ] = -arr[x - 1 ]; }//Return the first index value at which //is positive for (i = 0 ; i < size; i++) if (arr[i]> 0 ) return i + 1 ; //1 is added becuase indexes //start from 0return size + 1 ; }/* Find the smallest positive missing number in an array that contains both positive and negative integers */ static int findMissing( int arr[], int size) { //First separate positive and //negative numbers int shift = segregate(arr, size); int arr2[] = new int [size - shift]; int j = 0 ; for ( int i = shift; i < size; i++) { arr2[j] = arr[i]; j++; } //Shift the array and call //findMissingPositive for //positive part return findMissingPositive(arr2, j); } //main function public static void main(String[] args) { int arr[] = { 0 , 10 , 2 , - 10 , - 20 }; int arr_size = arr.length; int missing = findMissing(arr, arr_size); System.out.println( "The smallest positive missing number is " + missing); } }

python

''' Python program to find the smallest positive missing number '''''' Utility function that puts all non-positive (0 and negative) numbers on left side of arr[] and return count of such numbers ''' def segregate(arr, size): j = 0 for i in range (size): if (arr[i] < = 0 ): arr[i], arr[j] = arr[j], arr[i] j + = 1 # increment count of non-positive integers return j ''' Find the smallest positive missing number in an array that contains all positive integers ''' def findMissingPositive(arr, size):# Mark arr[i] as visited by making arr[arr[i] - 1] negative. # Note that 1 is subtracted because index start # from 0 and positive numbers start from 1 for i in range (size): if ( abs (arr[i]) - 1 < size and arr[ abs (arr[i]) - 1 ]> 0 ): arr[ abs (arr[i]) - 1 ] = - arr[ abs (arr[i]) - 1 ]# Return the first index value at which is positive for i in range (size): if (arr[i]> 0 ):# 1 is added because indexes start from 0 return i + 1 return size + 1''' Find the smallest positive missing number in an array that contains both positive and negative integers ''' def findMissing(arr, size):# First separate positive and negative numbers shift = segregate(arr, size)# Shift the array and call findMissingPositive for # positive part return findMissingPositive(arr[shift:], size - shift) # Driver code arr = [ 0 , 10 , 2 , - 10 , - 20 ] arr_size = len (arr) missing = findMissing(arr, arr_size) print ( "The smallest positive missing number is " , missing)# This code is contributed by Shubhamsingh10

C#

//C# program to find the smallest //positive missing number using System; class main {//Utility function that puts all //non-positive (0 and negative) //numbers on left side of arr[] //and return count of such numbers static int segregate( int [] arr, int size) { int j = 0, i; for (i = 0; i < size; i++) { if (arr[i] < = 0) { int temp; temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; //increment count of non-positive //integers j++; } }return j; }//Find the smallest positive missing //number in an array that contains //all positive integers static int findMissingPositive( int [] arr, int size) { int i; //Mark arr[i] as visited by making //arr[arr[i] - 1] negative. Note that //1 is subtracted as index start from //0 and positive numbers start from 1 for (i = 0; i < size; i++) { if (Math.Abs(arr[i]) - 1 < size & & arr[ Math.Abs(arr[i]) - 1]> 0) arr[ Math.Abs(arr[i]) - 1] = -arr[ Math.Abs(arr[i]) - 1]; }//Return the first index value at //which is positive for (i = 0; i < size; i++) if (arr[i]> 0) return i + 1; //1 is added becuase indexes //start from 0 return size + 1; }//Find the smallest positive //missing number in array that //contains both positive and //negative integers static int findMissing( int [] arr, int size) {//First separate positive and //negative numbers int shift = segregate(arr, size); int [] arr2 = new int [size - shift]; int j = 0; for ( int i = shift; i < size; i++) { arr2[j] = arr[i]; j++; }//Shift the array and call //findMissingPositive for //positive part return findMissingPositive(arr2, j); }//main function public static void Main() { int [] arr = { 0, 10, 2, -10, -20 }; int arr_size = arr.Length; int missing = findMissing(arr, arr_size); Console.WriteLine( "The smallest positive missing number is " + missing); } }//This code is contributed by Anant Agarwal.

输出如下：

The smallest positive missing number is 1

请注意, 此方法会修改原始数组。我们可以更改分隔数组中元素的符号, 以获取相同的元素集。但是我们仍然放宽元素的顺序。如果我们要保持原始数组不变, 则可以创建该数组的副本, 然后在temp数组上运行此方法。
另一种方法：在此问题中, 我们创建了一个全为0的列表, 其大小为给定数组的max()值。现在, 无论何时在原始数组中遇到任何正值, 我们都会将列表的索引值更改为1。因此, 完成后, 我们简单地遍历修改后的列表, 即遇到的第一个0, 即(索引值+ 1)应该是我们的答案, 因为python中的索引从0开始。
下面是上述方法的实现：
C ++

//C++ implementation of the approach #include < bits/stdc++.h> using namespace std; //Function to return the first missing positive //number from the given unsorted array int firstMissingPos( int A[], int n) {//To mark the occurrence of elements bool present[n + 1] = { false }; //Mark the occurrences for ( int i = 0; i < n; i++) {//Only mark the required elements //All non-positive elements and //the elements greater n + 1 will never //be the answer //For example, the array will be {1, 2, 3} //in the worst case and the result //will be 4 which is n + 1 if (A[i]> 0 & & A[i] < = n) present[A[i]] = true ; }//Find the first element which didn't //appear in the original array for ( int i = 1; i < = n; i++) if (!present[i]) return i; //If the original array was of the //type {1, 2, 3} in its sorted form return n + 1; }//Driver code int main() {int A[] = { 0, 10, 2, -10, -20 }; int size = sizeof (A) /sizeof (A[0]); cout < < firstMissingPos(A, size); }//This code is contributed by gp6

Java

//Java Program to find the smallest //positive missing number import java.util.Arrays; public class GFG {static int solution( int [] A) { int n = A.length; //To mark the occurrence of elements boolean [] present = new boolean [n + 1 ]; //Mark the occurrences for ( int i = 0 ; i < n; i++) {//Only mark the required elements //All non-positive elements and //the elements greater n + 1 will never //be the answer //For example, the array will be {1, 2, 3} //in the worst case and the result //will be 4 which is n + 1 if (A[i]> 0 & & A[i] < = n) present[A[i]] = true ; }//Find the first element which didn't //appear in the original array for ( int i = 1 ; i < = n; i++) if (!present[i]) return i; //If the original array was of the //type {1, 2, 3} in its sorted form return n + 1 ; }public static void main(String[] args) {int A[] = { 0 , 10 , 2 , - 10 , - 20 }; System.out.println(solution(A)); } } //This code is contributed by 29AjayKumar

Python 3

# Python Program to find the smallest # positive missing numberdef solution(A): # Our original arraym = max (A) # Storing maximum value if m < 1 :# In case all values in our array are negative return 1 if len (A) = = 1 :# If it contains only one element return 2 if A[ 0 ] = = 1 else 1 l = [ 0 ] * m for i in range ( len (A)): if A[i]> 0 : if l[A[i] - 1 ] ! = 1 :# Changing the value status at the index of our list l[A[i] - 1 ] = 1 for i in range ( len (l)):# Encountering first 0, i.e, the element with least value if l[i] = = 0 : return i + 1 # In case all values are filled between 1 and m return i + 2A = [ 0 , 10 , 2 , - 10 , - 20 ] print (solution(A))

C#

//C# Program to find the smallest //positive missing number using System; using System.Linq; class GFG { static int solution( int [] A) { //Our original arrayint m = A.Max(); //Storing maximum value//In case all values in our array are negative if (m < 1) { return 1; } if (A.Length == 1) {//If it contains only one element if (A[0] == 1) { return 2; } else { return 1; } } int i = 0; int [] l = new int [m]; for (i = 0; i < A.Length; i++) { if (A[i]> 0) { //Changing the value status at the index of our list if (l[A[i] - 1] != 1) { l[A[i] - 1] = 1; } } }//Encountering first 0, i.e, the element with least value for (i = 0; i < l.Length; i++) { if (l[i] == 0) { return i + 1; } }//In case all values are filled between 1 and m return i + 2; }//Driver code public static void Main() { int [] A = { 0, 10, 2, -10, -20 }; Console.WriteLine(solution(A)); } }//This code is contributed by PrinciRaj1992

的PHP

< ?php //PHP Program to find the smallest //positive missing numberfunction solution( $A ){ //Our original array$m = max( $A ); //Storing maximum value if ( $m < 1) { //In case all values in our array are negative return 1; } if (sizeof( $A ) == 1) { //If it contains only one element if ( $A [0] == 1) return 2 ; else return 1 ; } $l = array_fill (0, $m , NULL); for ( $i = 0; $i < sizeof( $A ); $i ++) { if ( $A [ $i ]> 0) { if ( $l [ $A [ $i ] - 1] != 1) {//Changing the value status at the index of our list $l [ $A [ $i ] - 1] = 1; } } } for ( $i = 0; $i < sizeof( $l ); $i ++) {//Encountering first 0, i.e, the element with least value if ( $l [ $i ] == 0) return $i +1; } //In case all values are filled between 1 and m return $i +2; }$A = array (0, 10, 2, -10, -20); echo solution( $A ); return 0; ?>

输出如下：

1

【查找未排序数组中缺失的最小正数|S1】如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请写评论。

推荐阅读

• 

  吃多少甘蔗可以缓解孕吐？
• 

  安和的寓意 安和的寓意解释
• 

  古人记录时间的方式 关于古人记录时间的方式
• 

  美乐家的四大系统
• 

  胆固醇|坏胆固醇低于3.4最理想
• 

  mysql安装没反应 mysql安装不了怎么办
• 

  时间管理smart案例分析,希赛公司某项目时间管理案例分析
• 

  我来分享autocad2022如何变成CAD经典
• 

  《道德经》原文
• 

  开心水族箱怎么升级快
• 

  柠檬水怎么泡是正确的泡法 柠檬片可以用开水泡吗
• 

  工作中群发邮件有什么策略吗？
• 

  联通|三星Z Flip3 5G奥运纪念版限量开售 携手联通共迎冬奥
• 

  薄荷叶泡水利尿吗
• 

  松饼小队什么梗
• 

  无尚是什么意思
• 

  Hse是什么意思
• 

  尼康换镜头以后无法拍照怎么回事 尼康换镜头以后无法拍照
• 

  蜜蜂的营养作用 蜜蜂的营养要求有哪些
• 

  辽参怎么泡发

• Salesforce面试经验|校园内
• Lex程序可计算行，空格和制表符的数量
• Win7可以不激活吗？Win7不激活会怎样样？
• spoon.sys损坏后，win7开机无法进入系统的处理办法
• win7系统关闭“交互式服务检测”提示窗口的办法
• win7定时开机的设置步骤
• 装win7开机出现checking media提示怎样办
• win7家庭版升级旗舰版办法与win7升级旗舰版密钥分享
• win7旗舰版出现蓝屏出错代码0x0000007A的处理办法