给定一个整数数组，找到线性时间和常数 space 中第一个缺失的正整数

Question

也就是说，找到数组中不存在的最小正整数。该数组也可以包含重复项和负数。这个问题是 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 变量保存尚未发生的最新最小正整数。你能想到更好的方法吗？提前致谢。

Answer 1

假设数组可以修改，

我们将数组分成两部分，第一部分只包含正数。假设我们的起始索引为 0，结束索引为 end（不包括）。
我们遍历数组从索引0到end。我们取该索引处元素的绝对值 - 假设值为 x.
1. 如果x > end我们什么都不做。
2. 如果不是，我们使索引 x-1 处的元素的符号为负。（澄清：我们不切换符号。如果值为正，则变为负。如果为负，则保持负。在伪代码中，这类似于 if (arr[x-1] > 0) arr[x-1] = -arr[x-1] 而不是 arr[x-1] = -arr[x-1].)
最后，我们再次遍历数组，从索引0到end。如果我们在某个索引处遇到正元素，我们输出 index + 1。这就是答案。但是，如果我们没有遇到任何正数元素，则意味着数组中出现了整数 1 到 end。我们输出 end + 1.

也可以是所有数都是非正数使得end = 0。输出 end + 1 = 1 保持正确。

所有步骤都可以在 O(n) 时间内完成并使用 O(1) space。

示例：

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+1 在数组中，我们将索引为 i 的元素的值更改为负数。

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

Answer 2

PMCarpan 的算法有效。

我认为你的方法可行，但你应该指定你正在做的排序类型，以便清楚它是线性排序而不一定是整个数组的完整排序。这导致 O(N) 时间不使用任何 space。

在扫描时扫描数组，如果当前索引中的值小于数组的长度，则将其与该索引中的当前值交换。您必须继续交换，直到在每个索引处交换不再有意义为止。然后在最后再进行一次扫描，直到找到不正确的索引。

这是一些工作 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:] 部分是因为根据您的描述，我们没有将零作为起点。

Answer 3

这是一个 C 实现
输入

#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
*/

Answer 4

#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))

Answer 5

我使用 python3 中的设置解决了这个问题。这是非常简单的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

Answer 6

我没有详细测试它，但对于排序数组，这是我的处理方式，欢迎任何改进。 约束：

线性时间

常量space

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(arr) 的零二进制数组 X。对于数组中的每个项目，将 X 的索引标记为 1 return 最小索引为 0

下面是满足

的简单实现

线性时间

恒定 space 复杂性约束。

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)

Answer 7

简单多了。（解决方案不是我的）

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;
}

有一个递归，但由于每个交换将 1 个值放到正确的位置，因此将有 <= n 个交换。线性时间

Answer 8

public int FindMissing(){
    var list = new int[] { 6, -6, 4, 5 };
    list = list.OrderBy(x => x).ToArray();
    var maxValue = 0;
    for (int i = 0; i < list.Length; i++)
    {
        if (list[i] <= 0)
        {
            continue;
        }
        if (i == list.Length - 1 ||
            list[i] + 1 != list[i + 1])
        {
            maxValue = list[i] + 1;
            break;
        }
    }
    return maxValue;
}

按升序排列数据：
for循环数据
- 如果值小于等于 0，则什么都不做并跳过。
- 检查当前索引值加1是否等于下一个索引值
  - 如果是，继续循环。
  - 如果没有，当前索引值加1就是缺失的正整数

Answer 9

这实际上是一个 LeetCode problem，它要求 O(n) 时间和 O(1) space，因此对输入进行排序或将其转换为集合是行不通的。这是的 Python 3 实现，它在 O(n) 时间内运行并使用 O(1) space.

def missing_int(nums: MutableSequence[int]) -> int:
    # If empty array or doesn't have 1, return 1
    if not next((x for x in nums if x == 1), 0):
        return 1

    lo: int = 0
    hi: int = len(nums) - 1
    i: int = 0
    pivot: int = 1

    while i <= hi:
        if nums[i] < pivot:
            swap(nums, i, hi)
            hi -= 1
        elif nums[i] > pivot:
            swap(nums, i, lo)
            i += 1
            lo += 1
        else:
            i += 1

    x = 0
    while x <= hi:  # hi is the index of the last positive number
        y: int = abs(nums[x])
        if 0 < y <= hi + 1 and nums[y - 1] > 0:  # Don't flip sign if already negative
            nums[y - 1] *= -1
        x += 1

    return next((i for i, v in enumerate(nums[:hi + 1]) if v >= 0), x) + 1

测试：

def test_missing_int(self):
    assert func.missing_int([1, 2, 1, 0]) == 3
    assert func.missing_int([3, 4, -1, 1]) == 2
    assert func.missing_int([7, 8, 9, 11, 12]) == 1
    assert func.missing_int([1]) == 2
    assert func.missing_int([]) == 1
    assert func.missing_int([0]) == 1
    assert func.missing_int([2, 1]) == 3
    assert func.missing_int([-1, -2, -3]) == 1
    assert func.missing_int([1, 1]) == 2
    assert func.missing_int([1000, -1]) == 1
    assert func.missing_int([-10, -3, -100, -1000, -239, 1]) == 2
    assert func.missing_int([1, 1]) == 2

Answer 10

JavaScript:

let findFirstMissingNumber = ( arr ) => {
      // Sort array and find the index of the lowest positive element.
      let sortedArr = arr.sort( (a,b) => a-b );
      const lowestPositiveIndex = arr.findIndex( (element) => element > 0 );

      // Starting from the lowest positive element
      // check upwards if we have the next integer in the array.
      let i = lowestPositiveIndex;
      while( i < sortedArr.length ) {
        if ( sortedArr[ i + 1 ] !== sortedArr[ i ] + 1 ) {
          return sortedArr[ i ] + 1
        } else {
          i += 1;
        }
      }
    }

    console.log( findFirstMissingNumber( [3, 4, -1, 1, 1] ) ); // should give 2
    console.log( findFirstMissingNumber( [0, 1, 2, 0] ) ); // should give 3

Answer 11

这是另一个 python 时间复杂度为 o(n) 且复杂度为 o(1) space 的实现

def segregate(arr):
    length = len(arr)
    neg_index = length
    for i, value in enumerate(arr):
        if(value < 1 and neg_index == length):
           neg_index = i
        if(neg_index != length and value >= 1):
           temp = arr[i]
           arr[i] = arr[neg_index]
           arr[neg_index] = temp
           neg_index += 1
    return arr[:neg_index]

def missingPositiveNumber(arr):
    arr = segregate(arr)
    length = len(arr)
    for i, value in enumerate(arr):
        if(value - 1 < l):
           arr[abs(value) - 1] = -(abs(arr[abs(value) - 1]))
    for i, value in enumerate(arr):
        if(value > 0):
           return i + 1
    return length + 1


print(missingPositiveNumber([1, -1, 2, 3]))

Answer 12

这是在 Java。时间复杂度 f O(N) 和 space 复杂度 O(1)

private static int minimum_positive_integer(int[] arr) {
        int i = 0;
        int j = arr.length - 1;

        //splitting array
        while (i < j) {
            if (arr[i] > 0) {
                i++;
            }

            if (arr[j] <= 0) {
                j--;
            }

            if (arr[i] <= 0 && arr[j] > 0) {
                int t = arr[i];
                arr[i] = arr[j];
                arr[j] = t;

                i++;
                j--;
            }
        }
        int len_positive = i;

        if (arr[i] > 0) len_positive++;

        for (i = 0; i < len_positive; i++) {
            int abs = Math.abs(arr[i]);
            if (abs <= len_positive) {
                int index = abs - 1;
                arr[index] = -abs;
            }
        }

        for (i = 0; i < len_positive; i++) {
            if(arr[i] > 0) return  i + 1;
        }

        return len_positive + 1;
    }

Answer 13

我在Python中的解决方案：

def lowest_positive(lista):

result = 0
dict = {}

for i in lista:

    if i <= 0:
        continue

    if i in dict:
        continue
    else:
        dict[i] = i

        if result == 0:
            result = result +1

        if result < i: 
            continue

        result = result +1

        while result in dict:
            result = result +1

return result

测试用例：

lista = [5, 3, 4, -1, 1, 2]
lista = [1,2,3,4,5]
lista = [3, 4, -1, 1]
lista = [2, 3, 4, 1]
lista = [1,0]
lowest_positive(lista)

请注意，我不认为 0 是正数

逻辑：number小于0则拒绝。然后在字典中检查该数字是否存在，如果存在，则读取下一个数字，否则将其添加到字典中。结果是一个一个递增的计数器。如果结果小于列表中读取的数字，则读取下一个数字，计数器加 1，并且此结果也在字典中检查。 Dictionary in all 将存储列表中读取的所有数字，以及列表中读取的最小数字之间任何缺失的正数。

Answer 14

上述方法的缺点是需要额外的 space 来分配“max_value”，这不是正确的解决方案

def missing_positive_integer(my_list):
    max_value = max(my_list)
    my_list = [num for num in range(1,max(my_list)) if num not in my_list]
    if len(my_list) == 0:
        my_list.append(max_value+1)

    return min(my_list)

my_list = [1,2,3,4,5,8,-1,-12,-3,-4,-8]
missing_positive_integer(my_list)

Answer 15

Javascript PMCarpan 算法的实现

function getMissingInt(array) {
  const segArray = array.filter((a) => a > 0);
  for (let i = 0; i < segArray.length; i++) {
    const value = Math.abs(segArray[i]);
    if (value <= segArray.length && segArray[value - 1] > 0) {
      segArray[value - 1] *= -1;
    }
  }
  for (let i = 0; i < segArray.length; i++) {
    if (segArray[i] > 0) {
      return i + 1;
    }
  }
  return segArray.length + 1;
}
console.log(getMissingInt([1, -1, -5, -3, 3, 4, 2, 8]));
console.log(getMissingInt([3, 4, -1, 1]));
console.log(getMissingInt([1, 2, 0]));

Answer 16

这是我在 leetcode 上接受的答案

    def firstMissingPositive(self, nums):
        if 1 not in nums:
            return 1
        n = len(nums)
        for i in range(n):
            if nums[i] > n or nums[i] <= 0:
                nums[i] = 1
        for i in range(n):
            a = abs(nums[i])
            if a == n:
                nums[0] = -abs(nums[0])
            else:
                nums[a] = -abs(nums[a])
        for i in range(2, n):
            if nums[i] > 0: return i
        return n if nums[0] > 0 else n+1

给定一个整数数组，找到线性时间和常数 space 中第一个缺失的正整数

Given an array of integers, find the first missing positive integer in linear time and constant space

arrays

sorting

algorithm

array-algorithms