在编码中查找缺少的整数

I need to "Find the minimal positive integer not occurring in a given sequence. "
  A[0] = 1    
  A[1] = 3    
  A[2] = 6
  A[3] = 4    
  A[4] = 1    
  A[5] = 2, the function should return 5.
Assume that:
        N is an integer within the range [1..100,000];
        each element of array A is an integer within the range [−2,147,483,648..2,147,483,647].

    class Solution {
    public int solution(int[] A) {
    if(A.Length ==0) return -1;
    int value = A[0];
    int min = A.Min();
    int max = A.Max();
    for (int j = min+1; j < max; j++)
    {
      if (!A.Contains(j))
      {
          value = j;
          if(value > 0)
          {
             break;
          }
      }
    }
    if(value > 0)
    {
      return value;
    }
    else return 1;
  }
}

编辑：添加了细节以更直接地回答您的实际问题。

"请帮帮我，我错在哪里。">

在正确性方面：考虑A = {7,2,5,6,3}.给定 A 的内容，正确的输出是 1 ，但是我们的算法将无法检测到这一点，因为 A.Min(( 会返回2并且我们会从3开始循环。在这种情况下，我们将返回4;因为它是下一个缺失值。

像A = {14,15,13}这样的事情也是如此。这里缺少的最小正整数再次1，并且由于 13-15 的所有值都存在，因此 value 变量将保留其初始值 value=A[0]，这将14 。

在性能方面：考虑A.Min()、A.Max()和A.Contains()在幕后做什么;每一个都在完整地循环A，在Contains的情况下，我们对Min()和我们能找到的最低正整数之间的每个值重复调用它。这将使我们远远超出Codility正在寻找的指定O(N)性能。

相比之下，这是我能想到的最简单的版本，在Codility上应该得分为100%。请注意，我们只循环遍历A一次，并且我们利用了一个允许我们使用ContainsKey的Dictionary;一种更快的方法，不需要遍历整个集合来查找值。

using System;
using System.Collections.Generic;
class Solution {
    public int solution(int[] A) {
        // the minimum possible answer is 1
        int result = 1; 
        // let's keep track of what we find
        Dictionary<int,bool> found = new Dictionary<int,bool>();
        // loop through the given array  
        for(int i=0;i<A.Length;i++) {
            // if we have a positive integer that we haven't found before
            if(A[i] > 0 && !found.ContainsKey(A[i])) {
                // record the fact that we found it
                found.Add(A[i], true);
            }
        }
        // crawl through what we found starting at 1
        while(found.ContainsKey(result)) {
            // look for the next number
            result++;
        }
        // return the smallest positive number that we couldn't find.
        return result;
    }
}

获得满分的最简单解决方案是：

public int solution(int[] A)
{
    int flag = 1;
    A = A.OrderBy(x => x).ToArray();
    for (int i = 0; i < A.Length; i++)
    {
        if (A[i] <= 0)
            continue;
        else if (A[i] == flag)
        {
            flag++;
        }
    }
    return flag;
}

迄今为止最快的 C# 解决方案，适用于 [-1,000,000

...1,000,000]。

public int solution(int[] array)
{
    HashSet<int> found = new HashSet<int>();
    for (int i = 0; i < array.Length; i++)
    {
        if (array[i] > 0)
        {
            found.Add(array[i]);
        }
    }
    int result = 1;
    while (found.Contains(result))
    {
        result++;
    }
    return result;
}

另一个

100% 的 C# 的微小版本

using System.Linq;
class Solution
{
    public int solution(int[] A)
    {
        // write your code in C# 6.0 with .NET 4.5 (Mono)
        var i = 0;
        return A.Where(a => a > 0).Distinct().OrderBy(a => a).Any(a => a != (i = i + 1)) ? i : i + 1;
    }
}

一个使用 C# 获得 100% 分数的简单解决方案

int Solution(int[] A)
    {            
        var A2 = Enumerable.Range(1, A.Length + 1);
        return A2.Except(A).First();
    }

public class Solution {
    public int solution( int[] A ) {
        return Arrays.stream( A )
                     .filter( n -> n > 0 )
                     .sorted()
                     .reduce( 0, ( a, b ) -> ( ( b - a ) > 1 ) ? a : b ) + 1;
    }
}

过滤

掉负数似乎最容易。然后对流进行排序。然后减少它以得出答案。这是一种功能方法，但它的测试分数为 100/100。

使用此解决方案获得了 100% 的分数：https://app.codility.com/demo/results/trainingUFKJSB-T8P/

   public int MissingInteger(int[] A)
    {
        A = A.Where(a => a > 0).Distinct().OrderBy(c => c).ToArray();
        if (A.Length== 0)
        {
            return 1;
        }
        for (int i = 0; i < A.Length; i++)
        {
            //Console.WriteLine(i + "=>" + A[i]);
            if (i + 1 != A[i])
            {
                return i + 1;
            }
        }
        return A.Max() + 1;
    }

JavaScript 解决方案，使用 Hash Table 且具有 O(n( 时间复杂度。

function solution(A) {
  let hashTable = {}
  for (let item of A) {
    hashTable[item] = true
  }
  let answer = 1
  while(true) {
    if(!hashTable[answer]) {
      return answer
    }
    answer++
  }
}

C# 最简单的解决方案是：

            int value = 1;
            int min = A.Min();
            int max = A.Max();
            if (A.Length == 0) return value = 1;
            if (min < 0 && max < 0) return value = 1;

            List<int> range = Enumerable.Range(1, max).ToList();
            List<int> current = A.ToList();
            List<int> valid = range.Except(current).ToList();
            if (valid.Count() == 0)
            {
                max++;
               return value = max;
            }
            else
            {
              return  value = valid.Min();
            }

Considering that the array should start from 1 or if it needs to start from the minimum value than the Enumerable.range should start from Min

C 语言中的 Missing Integer 解

int solution(int A[], int N) {
   int i=0,r[N];
   memset(r,0,(sizeof(r)));
   for(i=0;i<N;i++)
   {
       if(( A[i] > 0) && (A[i] <= N)) r[A[i]-1]=A[i];
   }
   for(i=0;i<N;i++)
   {
       if( r[i] != (i+1)) return (i+1);
   }
   return (N+1);
}

我的解决方案：

public static int solution()
    {
        var A = new[] { -1000000, 1000000 }; // You can try with different integers
        A = A.OrderBy(i => i).ToArray(); // We sort the array first
        if (A.Length == 1) // if there is only one item in the array
        {
            if (A[0]<0 || A[0] > 1)
                return 1;
            if (A[0] == 1)
                return 2;
        }
        else // if there are more than one item in the array
        {
            for (var i = 0; i < A.Length - 1; i++)
            {
                if (A[i] >= 1000000) continue; // if it's bigger than 1M
                if (A[i] < 0 || (A[i] + 1) >= (A[i + 1])) continue; //if it's smaller than 0, if the next integer is bigger or equal to next integer in the sequence continue searching.
                if (1 < A[0]) return 1;
                return A[i] + 1;
            }
        }
        if (1 < A[0] || A[A.Length - 1] + 1 == 0 || A[A.Length - 1] + 1 > 1000000)
            return 1;
        return A[A.Length-1] +1;
    }

class Solution {
    public int solution(int[] A) {
    int size=A.length;
    int small,big,temp;
    for (int i=0;i<size;i++){
        for(int j=0;j<size;j++){
            if(A[i]<A[j]){
                temp=A[j];
                A[j]=A[i];
                A[i]=temp;
            }
        }

    }   
    int z=1;
    for(int i=0;i<size;i++){
        if(z==A[i]){
            z++;
        }
        //System.out.println(a[i]);
    }
    return z;       
    }


enter code here
}

在 C# 中，您可以通过使用内置库函数来解决此问题。对于非常大的整数，性能如何低

public int solution(int[] A)
{
    var numbers = Enumerable.Range(1, Math.Abs(A.Max())+1).ToArray();
    return numbers.Except(A).ToArray()[0];
}

如果您找到更好的解决方案，请告诉我性能明智

C# - MissingInteger

查找 1 - 1000.000 之间的最小缺失整数。

OP的假设发生

任务得分/正确性/性能：100%

using System;
using System.Linq;
namespace TestConsole
{
    class Program
    {
        static void Main(string[] args)
        {
            var A = new int[] { -122, -5, 1, 2, 3, 4, 5, 6, 7 }; // 8
            var B = new int[] { 1, 3, 6, 4, 1, 2 }; // 5
            var C = new int[] { -1, -3 };  // 1
            var D = new int[] { -3 };  // 1
            var E = new int[] { 1 };  // 2
            var F = new int[] { 1000000 };  // 1

            var x = new int[][] { A, B, C, D, E, F };
            x.ToList().ForEach((arr) =>
            {
                var s = new Solution();
                Console.WriteLine(s.solution(arr));
            });
            Console.ReadLine();
        }
    }
 
    // ANSWER/SOLUTION
    class Solution
    {
        public int solution(int[] A)
        {
            // clean up array for negatives and duplicates, do sort
            A = A.Where(entry => entry > 0).Distinct().OrderBy(it => it).ToArray();
            int lowest = 1, aLength = A.Length, highestIndex = aLength - 1;
            for (int i = 0; i < aLength; i++)
            {
                var currInt = A[i];
                if (currInt > lowest) return lowest;
                if (i == highestIndex) return ++lowest;
                lowest++;
            }
            return 1;
        }
    }
}

获得 100% - C# 高效解决方案

     public int solution (int [] A){
        int len = A.Length;
        HashSet<int> realSet = new HashSet<int>();
        HashSet<int> perfectSet = new HashSet<int>();
        int i = 0;
        while ( i < len)
        {
            realSet.Add(A[i]);   //convert array to set to get rid of duplicates, order int's
            perfectSet.Add(i + 1);  //create perfect set so can find missing int
            i++;
        }
        perfectSet.Add(i + 1);
        if (realSet.All(item => item < 0))
            return 1;
        int notContains = 
         perfectSet.Except(realSet).Where(item=>item!=0).FirstOrDefault();
        return notContains;
}

class Solution {
  public int solution(int[] a) {
    int smallestPositive = 1;
    while(a.Contains(smallestPositive)) {
      smallestPositive++;
    }
    return smallestPositive;
  }
}

嗯，现在这是一个新的赢家。至少在 C# 和我的笔记本电脑上。它比之前的冠军快 1.5-2 倍，比大多数其他解决方案快 3-10 倍。此解决方案的功能(或错误？(是它仅使用基本数据类型。还有100/100关于法典。

public int Solution(int[] A)
{
    bool[] B = new bool[(A.Length + 1)];
    for (int i = 0; i < A.Length; i++)
    {
        if ((A[i] > 0) && (A[i] <= A.Length))
            B[A[i]] = true;
    }
    for (int i = 1; i < B.Length; i++)
    {
        if (!B[i])
            return i;
    }
    return A.Length + 1;
}

简单的C++解决方案。无需额外的内存，时间执行顺序 O(N*log(N((：

int solution(vector<int> &A) {
    sort (A.begin(), A.end());
    int prev = 0; // the biggest integer greater than 0 found until now
    for( auto it = std::begin(A); it != std::end(A); it++ ) {
        if( *it > prev+1  ) break;// gap found
        if( *it > 0 ) prev = *it; // ignore integers smaller than 1
    }
    return prev+1;    
}

    int[] A = {1, 3, 6, 4, 1, 2};
    Set<Integer> integers = new TreeSet<>();
    for (int i = 0; i < A.length; i++) {
        if (A[i] > 0) {
            integers.add(A[i]);
        }
    }
    Integer[] arr = integers.toArray(new Integer[0]);
    final int[] result = {Integer.MAX_VALUE};
    final int[] prev = {0};
    final int[] curr2 = {1};
    integers.stream().forEach(integer -> {
        if (prev[0] + curr2[0] == integer) {
            prev[0] = integer;
        } else {
            result[0] = prev[0] + curr2[0];
        }
    });
    if (Integer.MAX_VALUE == result[0]) result[0] = arr[arr.length-1] + 1;
    System.out.println(result[0]);

我很

惊讶，但这是一个很好的教训。林克很慢。我下面的答案让我得到 11%

public int solution (int [] A){
    if (Array.FindAll(A, x => x >= 0).Length == 0) {
        return 1;
    } else {
        var lowestValue = A.Where(x => Array.IndexOf(A, (x+1)) == -1).Min();
        return lowestValue + 1;
    }
}

我想我对此的看法有点不同，但得到了 100% 的评价。另外，我没有使用库：

public static int Solution(int[] A)
{
    var arrPos = new int[1_000_001];
    for (int i = 0; i < A.Length; i++)
    {
        if (A[i] >= 0)
            arrPos[A[i]] = 1;
    }
    for (int i = 1; i < arrPos.Length; i++)
    {
        if (arrPos[i] == 0)
            return i;
    }
    return 1;
}

public int solution(int[] A) {
        // write your code in Java SE 8
        Set<Integer> elements = new TreeSet<Integer>();
        long lookFor = 1;
        for (int i = 0; i < A.length; i++) {
            elements.add(A[i]);
        }
        for (Integer integer : elements) {
            if (integer == lookFor)
                lookFor += 1;
        }
        return (int) lookFor;
    }

我尝试在 C# 中使用递归而不是排序，因为我认为这样做会显示出更多的编码技能，但在扩展测试中，它在大型性能测试中表现不佳。假设最好只做简单的方法。

class Solution {
public int lowest=1;
public int solution(int[] A) {
    // write your code in C# 6.0 with .NET 4.5 (Mono)
    if (A.Length < 1)
        return 1;
     for (int i=0; i < A.Length; i++){
         if (A[i]==lowest){
            lowest++;
            solution(A);
         }
     }
     return lowest;  
    }
}

这是我

在javascript中的解决方案

function solution(A) {
    // write your code in JavaScript (Node.js 8.9.4)
    let result = 1;
    let haveFound = {}
    let len = A.length
    for (let i=0;i<len;i++) {
        haveFound[`${A[i]}`] = true
    }
    while(haveFound[`${result}`]) {
        result++
    }
    return result
}

class Solution {
    public int solution(int[] A) {
        var sortedList = A.Where(x => x > 0).Distinct().OrderBy(x => x).ToArray();
        var output = 1;
        
        for (int i = 0; i < sortedList.Length; i++)
        {
            if (sortedList[i] != output)
            {
                return output;
            }
            output++;
        }
        return output;
    }
}

你应该只使用HashSet，因为它的查找时间也是恒定的，而不是字典。代码更少更干净。

public int solution (int [] A){
    int answer = 1;
    var set = new HashSet<int>(A);
    while (set.Contains(answer)){
       answer++;
    }
    return answer;
}

此代码段应该可以正常工作。

using System;
using System.Collections.Generic;
public class Program
{
    public static void Main()
    {
     int result = 1;
     List<int> lst = new List<int>();
     lst.Add(1);
     lst.Add(2);
     lst.Add(3);
     lst.Add(18);
     lst.Add(4);
     lst.Add(1000);
     lst.Add(-1);
     lst.Add(-1000);
     lst.Sort();
     foreach(int curVal in lst)
     {
        if(curVal <=0)
            result=1;
        else if(!lst.Contains(curVal+1))
        {
            result = curVal + 1 ;
        }
        Console.WriteLine(result);
     }
    }
}