在Codility中找到缺少的整数

Question

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].

我在代码中编写了代码,但在许多情况下它没有用,性能测试给出了0%.请帮帮我,我错了.

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

除了示例,只有正面和负面的值之外,编码会给出所有错误.

Answer 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()我们可以找到的最小正整数之间的每个值.这将使我们远远超出O(N)Codility所寻求的指定性能.

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

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

Answer 2

迄今为止最快的 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;
}

Answer 3

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

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

Answer 4

另一个 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;
    }
}

Answer 5

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

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