返回数组中未出现的最小正整数（大于0）

Question

我有以下问题

写一个函数：

class Solution { public int solution(int[] A); }

给定一个包含N个整数的数组A，返回A中没有出现的最小正整数（大于0）。

例如，给定 A = [1， 3， 6， 4， 1， 2]，函数应返回 5。

给定A = [1，2，3]，函数应该返回4。

给定A =[1，3]，该函数应返回1。

为以下假设编写有效的算法：

• N是[1..100000]范围内的整数
• 数组A的每个元素都是范围内的整数[−1000000..1000000]

现在我尝试了这段代码：-

using System;
// you can also use other imports, for example:
// using System.Collections.Generic;

// you can write to stdout for debugging purposes, e.g.
// Console.WriteLine("this is a debug message");

class Solution
{
    public int solution(int[] A)
    {
        // write your code in C# 6.0 with .NET 4.5 (Mono)
        int n = 1;
        Array.Sort(A);
        for (int i = 1; i <= 100000; i++)
        {
            for (int i2 = 0; i2 <= A.Length - 1; i2++)
            {
                if (A[i2] == i)

                {
                    n = A[i2] + 1;
                    break;
                }

            }



        }
        return n;

    }
}

我的代码在这些测试数据中运行良好：-

A=[1,2,3]

A = [−1， −3]

虽然失败了：-

A = [1，3，6，4，1，2]，其中它返回7而不是5。

为什么我的代码在第三次测试中失败了，有什么建议吗？

谢啦

Answer 1

如果允许您对数组进行就地排序（这意味着修改输入参数值），那么这里有一个简单的线性探针，用于查找缺失的值（当然是排序的顶部）。

下面是伪代码：

Sort the array
Skip all negatives and 0's at the start
Loopify the following:
    Expect 1, if not found at current location return 1
    Skip all 1's
    Expect 2, if not found at current location return 2
    Skip all 2's
    Expect 3, if not found at current location return 3
    Skip all 3's
    ... and so on for 4, 5, 6, etc. until end of array
If we get here, return currently expected value which should've been at the end

代码如下：

public static int FirstMissingValue(int[] input)
{
    Array.Sort(input);
    
    int index = 0;
    
    // Skip negatives
    while (index < input.Length && input[index] < 1)
        index++;

    int expected = 1;
    while (index < input.Length)
    {
        if (input[index] > expected)
            return expected;
            
        // Skip number and all duplicates
        while (index < input.Length && input[index] == expected)
            index++;
            
        expected++;
    }
    
    return expected;
}

测试用例：

Console.WriteLine(FirstMissingValue(new[] { 1, 3, 6, 4, 1, 2 }));
Console.WriteLine(FirstMissingValue(new[] { 1, 2, 3 }));
Console.WriteLine(FirstMissingValue(new[] { -1, -3 }));

输出：

5
4
1

Answer 2

我将使用以下方法，使用HashSet

public static int? SmallestMissing(int[] A, int rangeStart = 1, int rangeEnd = 100_000)
{
     HashSet<int> hs = new HashSet<int>(A);
     for (int i = rangeStart; i <= rangeEnd; i++)
        if(!hs.Contains(i)) return i;
     
     return null;
}

如果值是唯一的，则HashSet是一个集合，它在查找项时非常有效（复杂性为O（1）.）。因此，您可以得到一个非常可读和高效的算法，但需要消耗一些内存。

也许您可以通过提供另一种算法来优化它，以防阵列非常大，您不想冒发生OutOfMemoryException的风险：

public static int? SmallestMissing(int[] A, int rangeStart = 1, int rangeEnd = 100_000)
{
    if(A.Length > 1_000_000)
    {
        Array.Sort(A);
        for (int i = rangeStart; i <= rangeEnd; i++)
        {
            int index = Array.BinarySearch(A, i);
            if(index < 0) return i;
        }
        return null;
    }
    
    HashSet<int> hs = new HashSet<int>(A);
    for (int i = rangeStart; i <= rangeEnd; i++)
        if(!hs.Contains(i)) return i;
 
    return null;
} 

Answer 3

using System.Linq;

int smallestNumber = Enumerable.Range(1, 100000).Except(A).Min();