换句话说，找到数组中不存在的最小正整数。该数组也可以包含重复数和负数。 Stripe在其编程访谈中询问了这个问题。我已经设计了一个解决方案，如下所示：
#include<bits/stdc++.h>
using namespace std;
int main(){
int arr[]={1,-1,-5,-3,3,4,2,8};
int size= sizeof(arr)/sizeof(arr[0]);
sort(arr, arr+size);
int min=1;
for(int i=0; i<size; i++){
if(arr[i]>min) break;
if(arr[i]==min) min=min+1;
}
cout<<min;
return 0;
}
在这里，我首先对数组进行排序，然后遍历数组一次。在遍历数组之前，我已经将名为“min”的变量初始化为1.现在，在遍历数组时，当我们得到一个等于min的整数时，我们只需增加min的值。这可确保min变量保持尚未发生的最新最小正整数。你能想到更好的方法吗？提前致谢。
假设阵列可以修改，
0，结束索引为end（不包括）。0到end。我们在该指数处取元素的绝对值 - 比如值为x。
如果x > end我们什么都不做。
如果没有，我们在索引x-1为负元素的符号。0到end遍历数组。如果我们在某个索引处遇到正元素，我们输出index + 1。这就是答案。但是，如果我们没有遇到任何正元素，则意味着整数1到end出现在数组中。我们输出end + 1。也可能是所有数字都是非正面的end = 0。输出end + 1 = 1保持正确。
所有步骤都可以在O(n)时间内完成并使用O(1)空间。
例：
Initial Array: 1 -1 -5 -3 3 4 2 8
Step 1 partition: 1 8 2 4 3 | -3 -5 -1, end = 5
在步骤2中，我们改变正数的符号以跟踪已经发生的整数。例如，在这里array[2] = -2 < 0，它表明2 + 1 = 3已经发生在数组中。基本上，如果i在数组中，我们将具有索引i+1的元素的值更改为负值。
Step 2 Array changes to: -1 -8 -2 -4 3 | -3 -5 -1
在步骤3中，如果某个值array[index]为正，则意味着我们在步骤2中未找到任何值index + 1的整数。
Step 3: Traversing from index 0 to end, we find array[4] = 3 > 0
The answer is 4 + 1 = 5
PMCarpan的算法有效。
我认为你的方法是有效的，但你应该指定你正在进行的排序类型，以便明确它是线性排序，而不一定是整个数组的完整排序。这导致O（N）时间而不使用任何空间。
扫描数组时，如果当前索引中的值小于数组的长度，则扫描数组，然后将其与当前索引中的值进行交换。您必须继续交换，直到交换每个索引不再有意义。然后在最后再做一次扫描，直到找到不正确的索引。
这里有一些工作的python代码，虽然python不是做这种事情的地方，哈哈。
def sortOfSort(arr) :
for index in range(len(arr)) :
checkValue = arr[index]
while(checkValue > 0 and checkValue != index and checkValue < len(arr) and arr[checkValue] != checkValue) :
arr[index] = arr[checkValue]
arr[checkValue] = checkValue
checkValue = arr[index]
return arr[1:] + [arr[0]]
def findFirstMissingNumber(arr) :
for x in range(len(arr)) :
if (x+1 != arr[x]) :
return x+1
return len(arr) + 1
return arr [1：]部分是因为根据你的描述我们不包括零作为起点。
这是一个C实现 INPUT
#include <stdio.h>
#include <stdlib.h>
//Here we separate the positive and negative number
int separate (int arr[], int size)
{
int j = 0, i , temp;
for(i = 0; i < size; i++)
{
if (arr[i] <= 0)
{
/*Here we using bitwise operator to swap the
numbers instead of using the temp variable*/
arr[j] = arr[j]^arr[i];
arr[i] = arr[j]^arr[i];
arr[j] = arr[j]^arr[i];
j++;
}
}
printf("First We Separate the negetive and positive number \n");
for( i = 0 ; i <size ; i++)
{
printf("Array[%d] = %d\n",i,arr[i]);
}
return j;
}
int findMissingPositive(int arr[], int size)
{
printf("Remove the negative numbers from array\n");
int i;
for( i = 0 ; i <size ; i++)
{
printf("Array[%d] = %d\n",i,arr[i]);
}
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];
}
for(i = 0; i < size; i++)
if (arr[i] > 0)
{
return i+1;
}
return size+1;
}
int findMissing(int arr[], int size)
{
int j = separate (arr, size);
return findMissingPositive(arr+j, size-j);
}
int main()
{
int size ;
printf("Enter the Value of Size of Array : ");
scanf("%d",&size);
int arr[size];
printf("Enter the values :\n");
for( int i = 0 ; i < size ; i++)
{
printf("Array[%d] = ",i);
scanf("%d",&arr[i]);
}
int missing = findMissing(arr,size);
printf("The smallest positive missing number is %d ", missing);
return 0;
}
Enter the Value of Size of Array : 8
Enter the values :
Array[0] = 1
Array[1] = -1
Array[2] = -5
Array[3] = -3
Array[4] = 3
Array[5] = 4
Array[6] = 2
Array[7] = 8
First We Separate the negetive and positive number
Array[0] = -1
Array[1] = -5
Array[2] = -3
Array[3] = 1
Array[4] = 3
Array[5] = 4
Array[6] = 2
Array[7] = 8
Remove the negative numbers from array
Array[0] = 1
Array[1] = 3
Array[2] = 4
Array[3] = 2
Array[4] = 8
The smallest positive missing number is 5
Process returned 0 (0x0) execution time : 27.914 s
Press any key to continue.
/*
How work :
[if(abs(arr[i]) - 1 < size && arr[ abs(arr[i]) - 1] > 0)
arr[ abs(arr[i]) - 1] = -arr[ abs(arr[i]) - 1];]
before: arr = { 7, 3, 4, 5, 5, 3, 2}
i == 0: arr[0] = 7
arr[7-1] is 2 > 0 ~> negate
arr = { 7, 3, 4, 5, 5, 3, -2}
i == 1: arr[1] = 3
arr[3-1] is 4 > 0 ~> negate
arr = { 7, 3, -4, 5, 5, 3, -2}
i == 2: arr[2] is -4 ~> abs for indexing
arr[4-1] is 5 > 0 ~> negate
arr = { 7, 3, -4,-5, 5, 3, -2}
i == 3: arr[3] is -5 ~> abs for indexing
arr[5-1] is 5 > 0 ~> negate
arr = { 7, 3, -4, -5, -5, 3, -2}
i == 4: arr[4] is -5 ~> abs for indexing
arr[5-1] is -5 < 0 ~> print abs(-5) as duplicate
i == 5: arr[5] is 3
arr[3-1] is -4 < 0 ~> print abs(3) as duplicate
i == 6: arr[6] is -2 ~> abs for indexing
arr[2-1] is 3 > 0 ~> negate
arr = { 7, -3, -4, -5, -5, 3, -2}
indices of positive entries: 0, 5 ~> 1 and 6 not in original array
indices of negative entries: 1, 2, 3, 4, 6 ~> 2, 3, 4, 5, 7 in original array
*/
#Returns a slice containing positive numbers
def findPositiveSubArr(arr):
negativeIndex = 0
if i in range(len(arr)):
if arr[i] <=0:
arr.insert(negativeIndex, arr.pop(i))
negativeIndex += 1
return arr[negativeIndex:]
#Returns the first missing positive number
def findMissingPositive(positiveArr):
l = len(positiveArr)
for num in positiveArr:
index = abs(num) - 1
if index < 1 and positiveArr[index] > 0:
positiveArr[index] *= -1
for i in range(l):
if positiveArr[i] > 0:
return i+1
return l+1
if __name__ == "__main__":
arr = [int(x) for x in input().strip().split()]
positiveSubArr = findPositveSubArr(arr)
print(findMissingPositive(positiveSubArr))
我在python3中使用set解决了这个问题。这是非常简单的6LOC。时间复杂度：O（n）。
记住：成员资格检查集是O（1）
def first_missing_positive_integer(arr):
arr = set(arr)
for i in range(1, len(arr)+2):
if i not in arr:
return i
它简单得多。 （解决方案不是我的）
public static int Missing(int[] a)
{
// the idea is to put all values in array on their ordered place if possible
for (int i = 0; i < a.Length; i++)
{
CheckArrayAtPosition(a, i);
}
for (int i = 0; i < a.Length; i++)
if (a[i] != i + 1)
return i + 1;
return a.Length + 1;
}
private static void CheckArrayAtPosition(int[] a, int i)
{
var currentValue = a[i];
if (currentValue < 1) return; // do not touch negative values because array indexes are non-negative
if (currentValue > a.Length) return; // do not touch values that are bigger than array length because we will not locate them anyway
if (a[currentValue - 1] == currentValue) return; // do not need to change anything because index contain correct value already
Swap(a, i, currentValue - 1);
CheckArrayAtPosition(a, i); // now current position value is updated so we need to check current position again
}
private static void Swap(int[] a, int i, int j)
{
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
有一个递归，但由于每个Swap将1个值放到正确的位置，因此将有<= n个交换。线性时间
蟒蛇：
if __name__ == '__main__':
# Read input, numbers separated by commas
numbers = [int(n) for n in input().split(',')]
numbers.sort()
next_number = 1
for n in numbers:
if n > 0:
if n > next_number:
break
else:
next_number = n + 1
print(next_number)
我没有对它进行详细测试，但是对于排序数组，我将如何处理它，欢迎任何改进。限制：
solution:
start with lowest positive integer (i.e. lpi <- 1)
while parsing the array, if lpi is already in the array, increment it
lpi现在是数组中不可用的最低正整数
简单的python函数如下：
def find_lpi(arr):
lpi = 1
for i in arr:
if lpi == i:
lpi += 1
return lpi
如果数组未排序，则以下可能是替代解决方案。
首先创建一个长度为max（array）的零的二进制数组X.对于数组中的每个项目标记X的索引，为1将最小的索引返回0
以下是一个令人满意的简单实现
def find_lpi(arr):
x = [0 for x in range(max(arr)+1)]
for i in arr:
x[i] = 1
for i in range(1,len(x)):
if x[i] ==0:
return i
return len(x)