时间戳

首页 > 解决方案 > 返回 Array 中未出现的最小正整数（大于 0）

c# - 返回 Array 中未出现的最小正整数（大于 0）

问题描述

我有以下问题：-

写一个函数：

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。

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

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

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。

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

谢谢

标签： c#arrays

解决方案

我将使用以下方法HashSet<int>来检查是否缺少给定的整数：

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

AHashSet是唯一值的集合，并且在查找项目时非常有效（复杂度为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;
}

推荐阅读