给定一个整数数组，在线性时间和恒定空间中找到第一个缺失的正整数 [英] Given an array of integers, find the first missing positive integer in linear time and constant space

问题描述

换句话说，找到数组中不存在的最低正整数.该数组也可以包含重复项和负数. Stripe在编程采访中曾问过这个问题.我已经针对以下问题设计了解决方案:

In other words, find the lowest positive integer that does not exist in the array. The array can contain duplicates and negative numbers as well. This question was asked by Stripe in it's programming interview. I have devised a solution for the same as below:

#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变量保存尚未出现的最新的最小正整数. 您能想到更好的方法吗?预先感谢.

Here, I am first sorting the array, and then traversing the array once. Before traversing the array, I have initialized a variable named "min" as 1. Now, while traversing the array, when we get an integer that is equal to min, we simply increment the value of min. This ensures that the min variable hold the latest least positive integer that has not occurred yet. Can you think of any better approach? Thanks in advance.

推荐答案

假定可以修改数组，

1. 我们将数组分为两部分，使得第一部分仅包含正数.假设我们的起始索引为0，结束索引为end(不包含).

1. We divide the array into 2 parts such that the first part consists of only positive numbers. Say we have the starting index as 0 and the ending index as end(exclusive).

我们遍历数组从索引0到end.我们在该索引处获取元素的绝对值-假设该值为x.

We traverse the array from index 0 to end. We take the absolute value of the element at that index - say the value is x.

1. 如果x > end，我们什么也不做.
2. 如果不是，则使索引x-1处的元素的符号为负.

1. If x > end we do nothing.
2. If not, we make the sign of the element at index x-1 negative.

最后，我们再次从索引0到end遍历数组.如果我们在某个索引处遇到一个正数元素，则输出index + 1.这就是答案.但是，如果我们没有遇到任何正数元素，则意味着整数1至end出现在数组中.我们输出end + 1.

Finally, we traverse the array once more from index 0 to end. In case we encounter a positive element at some index, we output index + 1. This is the answer. However, if we do not encounter any positive element, it means that integers 1 to end occur in the array. We output end + 1.

所有数字均为非正数的情况也可能是end = 0.输出end + 1 = 1保持正确.

It can also be the case that all the numbers are non-positive making end = 0. The output end + 1 = 1 remains correct.

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

All the steps can be done in O(n) time and using 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的元素的值更改为负.

In step 2 we change the signs of the positive numbers to keep track of which integers have already occurred. For example, here array[2] = -2 < 0, it suggests that 2 + 1 = 3 has already occurred in the array. Basically, we change the value of the element having index i to negative if i+1 is in the array.

Step 2 Array changes to: -1 -8 -2 -4 3 | -3 -5 -1

在第3步中，如果某个值array[index]为正，则意味着在第2步中没有找到任何值index + 1的整数.

In step 3, if some value array[index] is positive, it means that we did not find any integer of value index + 1 in step 2.

Step 3: Traversing from index 0 to end, we find array[4] = 3 > 0
        The answer is 4 + 1 = 5

这篇关于给定一个整数数组，在线性时间和恒定空间中找到第一个缺失的正整数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！