Найдите наименьшее положительное целое число, которое не встречается в данной последовательности

Если ожидаемое время работы должно быть линейным, вы не можете использовать TreeSet, который сортирует ввод и поэтому требует O(NlogN). Поэтому вам следует использовать HashSet, которому требуется время O(N) для добавления элементов N.

К тому же вам не нужно 4 петли. Достаточно добавить все положительные входные элементы в HashSet (первый цикл), а затем найти первое положительное целое число, не входящее в этот набор (второй цикл).

int N = A.length;
Set<Integer> set = new HashSet<>();
for (int a : A) {
    if (a > 0) {
        set.add(a);
    }
}
for (int i = 1; i <= N + 1; i++) {
    if (!set.contains(i)) {
        return i;
    }
}

Ты слишком много делаешь. Вы создали TreeSet, который представляет собой упорядоченный набор целых чисел, а затем попытались превратить его обратно в массив. Вместо этого просмотрите список и пропустите все отрицательные значения, а затем, как только вы найдете положительные значения, начните подсчет индекса. Если индекс больше числа, значит, в наборе пропущено положительное значение.

int index = 1;
for(int a: set){
    if (a>0){
        if (a>index){
            return index;
        } else{
            index++;
        }
    }
}
return index;

Обновлено для отрицательных значений.

Другое решение - O (n) - использовать массив. Это похоже на хеш-решение.

int N = A.length;
int[] hashed = new int[N];

for( int i: A){
    if (i>0 && i<=N){
        hashed[i-1] = 1;
    }
}

for(int i = 0; i<N; i++){
    if (hash[i]==0){
        return i+1;
    }
}
return N+1;

Это может быть дополнительно оптимизировано путем обратного отсчета верхнего предела для второго цикла.

Для пространственной сложности O(1) и временной сложности O(N), и если массив может быть изменен, он может быть следующим:

public int getFirstSmallestPositiveNumber(int[] arr) {
    // set positions of non-positive or out of range elements as free (use 0 as marker)
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] <= 0 || arr[i] > arr.length) {
            arr[i] = 0;
        }
    }

    //iterate through the whole array again mapping elements [1,n] to positions [0, n-1]
    for (int i = 0; i < arr.length; i++) {
        int prev = arr[i];
        // while elements are not on their correct positions keep putting them there
        while (prev > 0 && arr[prev - 1] != prev) {
            int next = arr[prev - 1];
            arr[prev - 1] = prev;
            prev = next;
        }
    }

    // now, the first unmapped position is the smallest element
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] != i + 1) {
            return i + 1;
        }
    }
    return arr.length + 1;
}

@Test
public void testGetFirstSmallestPositiveNumber() {
    int[][] arrays = new int[][]{{1,-1,-5,-3,3,4,2,8},
      {5, 4, 3, 2, 1}, 
      {0, 3, -2, -1, 1}};

    for (int i = 0; i < arrays.length; i++) {
        System.out.println(getFirstSmallestPositiveNumber(arrays[i]));
    }
}  

Выход:

5

6

2

Я нахожу другое решение сделать это с дополнительным хранилищем,

/*
* if A = [-1,2] the solution works fine
* */
public static int solution(int[] A) {

    int N = A.length;

    int[] C = new int[N];

    /*
     * Mark A[i] as visited by making A[A[i] - 1] negative
     * */
    for (int i = 0; i < N; i++) {

        /*
         * we need the absolute value for the duplicates
         * */
        int j = Math.abs(A[i]) - 1;

        if (j >= 0 && j < N && A[j] > 0) {
            C[j] = -A[j];
        }
    }

    for (int i = 0; i < N; i++) {

        if (C[i] == 0) {
            return i + 1;
        }
    }

    return N + 1;
}

Не нужно ничего хранить. Не нужны хеш-наборы. (Дополнительная память), вы можете сделать это как вы перемещаться по массиву. Однако массив необходимо отсортировать. И мы знаем, что самое минимальное значение - 1

import java.util.Arrays;
class Solution {
    public int solution(int[] A) {
        Arrays.sort(A);     
        int min = 1; 
        int cap = A.length; //for efficiency — no need to calculate or access the array object’s length property per iteration 
        
        for (int i = 0; i < cap; i++){
            if (A[i] == min){
                min++;
            }//can add else if A[i] > min, break; as suggested by punit
        }   
        //min = ( min <= 0 ) ? 1:min; //this means: if (min <= 0 ){min =1}else{min = min} you can also do: if min <1 for better efficiency/less jumps
        return min;    
    }
}

//My recursive solution:

class Solution {
    public int solution(int[] A) {
        return next(1, A);
    }
    public int next(int b, int[] A) {
        for (int a : A){
            if (b==a)
                return next(++b, A);
        }
        return b;
    }
}

Поздно присоединиться к разговору. По материалам:

https://codereview.stackexchange.com/a/179091/184415

Действительно, существует решение этой проблемы со сложностью O (n), даже если во входных данных задействованы повторяющиеся целые числа:

solution(A)
Filter out non-positive values from A
For each int in filtered
    Let a zero-based index be the absolute value of the int - 1
    If the filtered range can be accessed by that index  and  filtered[index] is not negative
        Make the value in filtered[index] negative

For each index in filtered
    if filtered[index] is positive
        return the index + 1 (to one-based)

If none of the elements in filtered is positive
    return the length of filtered + 1 (to one-based)

So an array A = [1, 2, 3, 5, 6], would have the following transformations:

abs(A[0]) = 1, to_0idx = 0, A[0] = 1, make_negative(A[0]), A = [-1,  2,  3,  5,  6]
abs(A[1]) = 2, to_0idx = 1, A[1] = 2, make_negative(A[1]), A = [-1, -2,  3,  5,  6]
abs(A[2]) = 3, to_0idx = 2, A[2] = 3, make_negative(A[2]), A = [-1, -2, -3,  5,  6]
abs(A[3]) = 5, to_0idx = 4, A[4] = 6, make_negative(A[4]), A = [-1, -2, -3,  5, -6]
abs(A[4]) = 6, to_0idx = 5, A[5] is inaccessible,          A = [-1, -2, -3,  5, -6]

A linear search for the first positive value returns an index of 3. Converting back to a one-based index results in solution(A)=3+1=4

Вот реализация предложенного алгоритма на C# (должна быть тривиальной, чтобы преобразовать его в язык Java - избавьте меня от некоторой слабости):

public int solution(int[] A)
{
    var positivesOnlySet = A
        .Where(x => x > 0)
        .ToArray();

    if (!positivesOnlySet.Any())
        return 1;

    var totalCount = positivesOnlySet.Length;
    for (var i = 0; i < totalCount; i++) //O(n) complexity
    {
        var abs = Math.Abs(positivesOnlySet[i]) - 1;
        if (abs < totalCount && positivesOnlySet[abs] > 0) //notice the greater than zero check 
            positivesOnlySet[abs] = -positivesOnlySet[abs];
    }

    for (var i = 0; i < totalCount; i++) //O(n) complexity
    {
        if (positivesOnlySet[i] > 0)
            return i + 1;
    }

    return totalCount + 1;
}

Я думаю, что использование таких структур, как: sets или dicts для хранения уникальных значений, не является лучшим решением, потому что вы заканчиваете либо поиск элемента внутри цикла, который приводит к сложности O (N * N), либо использование другого цикла для проверки отсутствующих значение, которое оставляет вам линейную сложность O (N), но тратит больше времени, чем просто 1 цикл.

Также использование структуры массива счетчиков не является оптимальным с точки зрения места для хранения, потому что вы в конечном итоге выделяете блоки памяти MaxValue, даже если в вашем массиве только один элемент.

Поэтому я думаю, что лучшее решение использует только один цикл for, избегая структур, а также реализуя условия для остановки итерации, когда она больше не нужна:

public int solution(int[] A) {
    // write your code in Java SE 8
    int len = A.length;
    int min=1;
    
    Arrays.sort(A);

    if (A[len-1]>0)
    for(int i=0; i<len; i++){
        if (A[i]>0){
            if (A[i]==min) min=min+1;
            if (A[i]>min) break;
        }
    }
    return min;
}

Таким образом, вы получите сложность O (N) или O (N * log (N)), поэтому в лучшем случае вы находитесь под сложностью O (N), когда ваш массив уже отсортирован

Попробуйте этот код, он работает для меня

import java.util.*;
    class Solution {
        public static int solution(int[] A) {
            // write your code in Java SE 8
            int m = Arrays.stream(A).max().getAsInt(); //Storing maximum value 
            if (m < 1) // In case all values in our array are negative 
            { 
                return 1; 
            } 
            if (A.length == 1) { 

                //If it contains only one element 
                if (A[0] == 1) { 
                    return 2; 
                } else { 
                    return 1; 
                } 
            } 
            int min = A[0];
            int max= A[0];
            int sm = 1;

            HashSet<Integer> set = new HashSet<Integer>();

            for(int i=0;i<A.length;i++){
                set.add(A[i]);

                if (A[i]<min){
                    min = A[i];
                }
                if (A[i]>max){
                    max = A[i];
                }
            }

            if (min <= 0){
                min = 1;
            }

            if (max <= 0){
                max = 1;
            }

            boolean fnd = false;
            for(int i=min;i<=max;i++){
                if (i>0 && !set.contains(i)){
                    sm = i;
                    fnd = true;
                    break;
                }
                else continue;

            }
            if (fnd)
                return sm; 
            else return max +1;
        }

              public static void main(String args[]){

               Scanner s=new Scanner(System.in);

            System.out.println("enter number of elements");

            int n=s.nextInt();

            int arr[]=new int[n];

            System.out.println("enter elements");

            for(int i=0;i<n;i++){//for reading array
                arr[i]=s.nextInt();

            }

        int array[] = arr;

        // Calling getMax() method for getting max value
        int max = solution(array);
        System.out.println("Maximum Value is: "+max);

      }
    }

Самый простой способ использования цикла while:

fun solution(A: IntArray): Int {
    var value = 1
    var find = false
    while(value < A.size) {
        val iterator = A.iterator()
        while (iterator.hasNext()) {
            if (value == iterator.nextInt()) {
                find = true
                value++
            }
        }
        if (!find) {
            break
        } else {
            find = false
        }
    }
    return value
}

Это может вам помочь, должно работать нормально!

public static int sol(int[] A)
{
    boolean flag =false;
    for(int i=1; i<=1000000;i++ ) {
        for(int j=0;j<A.length;j++) {
            if (A[j]==i) {
                flag = false;
                break;
            }else {
                flag = true;
            }
        }
        if (flag) {
            return i;
        }
    }
    return 1;
}

package Consumer;


import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;

public class codility {
public static void main(String a[])
    {
        int[] A = {1,9,8,7,6,4,2,3};
        int B[]= {-7,-5,-9};
        int C[]  = {1,-2,3};
        int D[]  = {1,2,3};
        int E[] = {-1};
        int F[] = {0};
        int G[] = {-1000000};
        System.out.println(getSmall(F));
    }
    public static int getSmall(int[] A)
    {
        int j=0;
        if (A.length < 1 || A.length > 100000) return -1;
        List<Integer> intList = Arrays.stream(A).boxed().sorted().collect(Collectors.toList());
         if (intList.get(0) < -1000000 || intList.get(intList.size()-1) > 1000000) return -1;
         if (intList.get(intList.size()-1) < 0) return 1;
        int count=0;         
         for(int i=1; i<=intList.size();i++)
         {
             if (!intList.contains(i))return i;
             count++;
         }
         if (count==intList.size()) return ++count;
        return -1;
    } 
}

    public int solution(int[] A) {

    int res = 0;
    HashSet<Integer> list = new HashSet<>();

    for (int i : A) list.add(i);
    for (int i = 1; i < 1000000; i++) {
        if (!list.contains(i)){
            res = i;
            break;
        }
    }
    return res;
}

Реализация решения на Python. Получить набор массива - это гарантирует, что у нас будут только уникальные элементы. Затем продолжайте проверять, пока значение не появится в наборе - Распечатайте следующее значение в качестве вывода и верните его.

def solution(A):
# write your code in Python 3.6
    a = set(A)
    i = 1
    while True:
        if i in A:
            i+=1
        else:
            return i
    return i
    pass

Работает на 100%. протестирован со всеми условиями, как описано.

//MissingInteger
    public int missingIntegerSolution(int[] A) {
        Arrays.sort(A);
        long sum = 0;
        for(int i=0; i<=A[A.length-1]; i++) {
            sum += i;
        }


        Set<Integer> mySet = Arrays.stream(A).boxed().collect(Collectors.toSet());
        Integer[] B = mySet.toArray(new Integer[0]);
        if (sum < 0)
            return 1;

        for(int i=0; i<B.length; i++) {
            sum -= B[i];
        }

        if (sum == 0) 
            return A[A.length-1] + 1;
        else
            return Integer.parseInt(""+sum);
    }

int[] j = {1, 3, 6, 4, 1, 2,5};

System.out.println("Missing Integer : "+obj.missingIntegerSolution(j));

На выходе отсутствует целое число: 7

int[] j = {1, 3, 6, 4, 1, 2};
System.out.println("Missing Integer : "+obj.missingIntegerSolution(j));

Выходное отсутствующее целое число: 5

Это решение на C#, но завершите тест со 100% результатом.

public int solution(int[] A) {
    // write your code in C# 6.0 with .NET 4.5 (Mono)
    var positives = A.Where(x => x > 0).Distinct().OrderBy(x => x).ToArray();
    if (positives.Count() == 0) return 1;
    int prev = 0;
    for(int i =0; i < positives.Count(); i++){

        if (positives[i] != prev + 1){
            return prev + 1;
        }
         prev = positives[i];
    }
    return positives.Last() + 1;
}

Вот мое решение PHP, 100% оценка задачи, 100% правильность и 100% производительность. Сначала мы повторяем и сохраняем все положительные элементы, затем проверяем, существуют ли они,

function solution($A) {

    $B = [];
    foreach($A as $a){ 
        if ($a > 0) $B[] = $a;   
    }

    $i = 1;
    $last = 0;
    sort($B);

    foreach($B as $b){

        if ($last == $b) $i--; // Check for repeated elements
        else if ($i != $b) return $i;

        $i++;
        $last = $b;        

    }

    return $i;
}

Я думаю, что это одна из самых простых и понятных функций здесь, логика может быть применена на всех других языках.

Простой способ сделать это !!

public int  findNearestPositive(int array[])
{
    boolean isNegative=false;
    int number=0;
    int value=0;

    if (array[0]<=0 && array[array.length-1]<0)
    {
    return 1;


    }

    for(int i=0;i<array.length;i++)
    {
    value=i+1;
    isNegative=false;

    for(int j=0;j<array.length;j++)
    {
    if (value==array[j])
    {
    isNegative=true;

    }

    }

    if (isNegative!=true)
    {
    if (number==0){

    number=value;
    }else if (value<number){
    number=value;
    }

    }               

    }


    if (number==0)
    {

    number=value+1;
    }

    return number;

}

Я достиг 100% в этом решении на Python: -

def solution(A):
   a=frozenset(sorted(A))
   m=max(a)
   if m>0:
       for i in range(1,m):
           if i not in a:
              return i
       else:
          return m+1
   else:
       return 1

Для JavaScript я бы сделал это так:

function solution(arr)
{
    let minValue = 1;

    arr.sort();

    if (arr[arr.length - 1] > 0)
    {
        for (let i = 0; i < arr.length; i++)
        {
            if (arr[i] === minValue)
            {
                minValue = minValue + 1;
            }
            if (arr[i] > minValue)
            {
                break;
            }
        }
    }

    return minValue;
}

Протестировал его со следующими образцами данных:

console.info(solution([1, 3, 6, 4, 1, 2]));
console.info(solution([1, 2, 3]));
console.info(solution([-1, -3]));

Мое решение на JavaScript с использованием метода reduce ()

function solution(A) {
  // the smallest positive integer = 1
  if (!A.includes(1)) return 1;

  // greater than 1
  return A.reduce((accumulator, current) => {
    if (current <= 0) return accumulator
    const min = current + 1
    return !A.includes(min) && accumulator > min ? min : accumulator;
  }, 1000000)
}

console.info(solution([1, 2, 3])) // 4
console.info(solution([5, 3, 2, 1, -1])) // 4
console.info(solution([-1, -3])) // 1
console.info(solution([2, 3, 4])) // 1

https://codesandbox.io/s/the-smallest-positive-integer-zu4s2

<JAVA> Try this code-

private int solution(int[] A) {//Our original array

        int m = Arrays.stream(A).max().getAsInt(); //Storing maximum value
        if (m < 1) // In case all values in our array are negative
        {
            return 1;
        }
        if (A.length == 1) {

            //If it contains only one element
            if (A[0] == 1) {
                return 2;
            } else {
                return 1;
            }
        }
        int i = 0;
        int[] l = new int[m];
        for (i = 0; i < A.length; i++) {
            if (A[i] > 0) {
                if (l[A[i] - 1] != 1) //Changing the value status at the index of our list
                {
                    l[A[i] - 1] = 1;
                }
            }
        }
        for (i = 0; i < l.length; i++) //Encountering first 0, i.e, the element with least value
        {
            if (l[i] == 0) {
                return i + 1;
            }
        }
        //In case all values are filled between 1 and m
        return i+1;
    }
Input: {1,-1,0} , o/p: 2
Input: {1,2,5,4,6}, o/p: 3
Input: {-1,0,-2}, o/p: 1

100% решение результата в Javascript:

function solution(A) {
    // only positive values, sorted
    A = A.filter(x => x >= 1).sort((a, b) => a - b)

    let x = 1

    for(let i = 0; i < A.length; i++) {
        // if we find a smaller number no need to continue, cause the array is sorted
        if (x < A[i]) {
            return x
        }
        x = A[i] + 1
    }

    return x
}

Для Swift 4

func solution(_ A : [Int]) -> Int {
     var positive = A.filter { $0 > 0 }.sorted()
     var x = 1
     for val in positive{
    // if we find a smaller number no need to continue, cause the array is sorted
    if (x < val) {
        return x
    }
    x = val + 1
}
return x

}

Мой код на Java, 100% результат Codility

import java.util.*;

class Solution {
   public int solution(int[] arr) {
     int smallestInt = 1; 

    if (arr.length == 0) return smallestInt;

    Arrays.sort(arr);

    if (arr[0] > 1) return smallestInt;
    if (arr[ arr.length - 1] <= 0 ) return smallestInt; 

    for(int i = 0; i < arr.length; i++){
        if (arr[i] == smallestInt){ 
         smallestInt++;}    
    }

    return smallestInt;
}

}

Мой ответ на Руби

def smallest_pos_integer(arr)
  sorted_array = arr.select {|x| x >= 1}.sort
  res = 1

  for i in (0..sorted_array.length - 1)
    if res < sorted_array[i]
      return res
    end
    res = sorted_array[i] + 1
  end
  res
end

Мое решение, имеющее 100% -ный результат, совместимо с Swift 4.

func solution(_ A : [Int]) -> Int {
    let positive = A.filter { $0 > 0 }.sorted()
    var x = 1
    for val in positive{
        if (x < val) {
            return x
        }
        x = val + 1
    }
    return x
}

Самое короткое PHP-решение

function solution($A) {
    // write your code in PHP7.0
    $lastNum = 1;

    while(in_array($lastNum, $A)) {
        $lastNum++;
    }

    return $lastNum;
}

Это мой подход к Java. Временная сложность этого ответа составляет 2 * O (N), потому что я дважды перебираю массив A.

import java.util.HashMap;

public static final Integer solution(int[] A) {
    HashMap<Integer, Integer> map = new HashMap<>(A.length); //O(n) space

    for (int i : A) {
        if (!map.containsKey(i)) {
            map.put(i, i);
        }
    }

    int minorPositive = 100000;
    for (int i : A) {
        if (!map.containsKey(i + 1)) {
            if (i < minorPositive) {
                minorPositive = i + 1;
            }
        }
    }

    if (minorPositive < 0){
        minorPositive = 1;
    }
    return minorPositive;

}

Вот мое решение на C++. Он получил 100% баллов (100% правильность, 100% производительность) (после нескольких попыток;)). Он основан на простом принципе сравнения своих значений с их соответствующим индексом (после небольшой предварительной обработки, такой как сортировка). Я согласен с тем, что ваше решение слишком много работает; Четыре петли не нужно.

Шаги моего решения в основном:

1. Отсортируйте и удалите дубликаты. Здесь есть два возможных метода: первый использует std::sort, std::unique и erase, а второй использует std::set и тот факт, что набор сортирует себя и запрещает дубликаты.
2. Обрабатывайте крайние случаи, которых довольно много (я пропустил их изначально, из-за чего моя оценка поначалу была довольно низкой). Три крайних случая:
   • Все целые числа в исходном массиве были отрицательными
   • Все целые числа в исходном массиве были положительными и больше 1
   • В исходном массиве был только 1 элемент
3. Для каждого элемента проверьте, равно ли его значение! = Его index + 1. Первый элемент, для которого это верно, - это наименьшее пропущенное положительное целое число. Т.е. если vec.at(i) != i+1, то vec.at(i-1)+1 - это наименьшее пропущенное положительное целое число.
4. Если vec.at(i) != i+1 ложен для всех элементов в массиве, то в последовательности массива нет «пробелов», а наименьшее положительное целое число просто vec.back () + 1 (четвертый крайний случай, если хотите).

И код:

int solution(vector<int>& rawVec)
{
    //Sort and remove duplicates: Method 1
    std::sort(rawVec.begin(), rawVec.end());
    rawVec.erase(std::unique(rawVec.begin(), rawVec.end()), rawVec.end());

    //Sort and remove duplicates: Method 2
    // std::set<int> s(rawVec.begin(), rawVec.end());
    // rawVec.assign(s.begin(), s.end());

    //Remove all ints < 1
    vector<int> vec;
    vec.reserve(rawVec.size());
    for(const auto& el : rawVec)
    {
        if (el>0)
            vec.push_back(el);
    }

    //Edge case: All ints were < 1 or all ints were > 1
    if (vec.size()==0 or vec.at(0) != 1)
        return 1;

    //Edge case: vector contains only one element
    if (vec.size()==1)
        return (vec.at(0)!=1 ? 1 : 2);

    for(int i=0; i<vec.size(); ++i)
    {
        if (vec.at(i) != i+1)
            return vec.at(i-1)+1;
    }
    return vec.back()+1;
}

Этот код был написан на Java SE 8

import java.util.*;

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

        int smallestPositiveInt = 1; 

        if (A.length == 0) {
            return smallestPositiveInt;
        }

        Arrays.sort(A);

        if (A[0] > 1) {
            return smallestPositiveInt;
        }

        if (A[A.length - 1] <= 0 ) {
            return smallestPositiveInt;
        }

        for(int x = 0; x < A.length; x++) {
            if (A[x] == smallestPositiveInt) { 
                smallestPositiveInt++;
             }    
        }

        return smallestPositiveInt;
    }
}

public static int solution(int[] A) {
    Arrays.sort(A);
    int minNumber = 1;
    int length = A.length - 1;
    int max = A[length];
    Set < Integer > set = new HashSet < > ();
    for (int i: A) {
        if (i > 0) {
            set.add(i);
        }
    }
    for (int j = 1; j <= max + 1; j++) {
        if (!set.contains(j)) {
            minNumber = j;
            break;
        }
    }
    return minNumber;
}

Это очень хорошо работает для java. Он использует побитовое исключающее ИЛИ и оператор присваивания.

    public int solution(int[] A) {
        // write your code in Java SE 8
        int sol = 0;
        for(int val:A){
            sol ^= val;
        }
        return sol;
    }
}

Мое решение:

  public int solution(int[] A) {
        int N = A.length;
        Set<Integer> set = new HashSet<>();
        for (int a : A) {
            if (a > 0) {
                set.add(a);
            }
        }
        for (int index = 1; index <= N; index++) {
            if (!set.contains(index)) {
                return index;
            }
        }
        return N + 1;
    }

В C# требуется улучшение.

    public int solution(int[] A) {
          int retorno = 0;
          for (int i = 0; i < A.Length; i++)
            {
                int ultimovalor = A[i] + 1;
                if (!A.Contains(ultimovalor))
                {
                    retorno = (ultimovalor);
                    if (retorno <= 0) retorno = 1;
                }
            }
            return retorno;
    }

// you can also use imports, for example:
// import java.util.*;

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

class Solution {
    public int solution(int[] A) {
    int size=A.length;
    int min=A[0];
    for(int i=1;i<=size;i++){
        boolean found=false;
        for(int j=0;j<size;j++){
            if (A[j]<min){min=A[j];}
            if (i==A[j]){
                found=true;
            }
        }
            if (found==false){
                return i;

            }
        }

    if (min<0){return 1;}
        return size+1;



    }
}

В Котлине с рейтингом% 100 Обнаруженная временная сложность: O (N) или O (N * log (N))

fun solution(A: IntArray): Int {
    var min = 1
    val b = A.sortedArray()
    for (i in 0 until b.size) {
        if (b[i] == min) {
            min++
        }
    }
    return min
}

def solution(A):
A = sorted(filter(lambda x: x >= 0, A))
if A is []:
    return 1
for i in range(1, 100000):
    if i not in A:
        return i

100% решение результата в Javascript:

function solution(A) {
 let N,i=1;
    A = [...new Set(A)]; // remove duplicated numbers form the Array
    A = A.filter(x => x >= 1).sort((a, b) => a - b); //  remove negative numbers & sort array
    while(!N){ // do not stop untel N get a value
      if (A[i-1] != i){N=i} 
      i++;
    }
    return N;
}

Вот эффективное решение для Python:

def solution(A):
    m = max(A)
    if m < 1:
       return 1

    A = set(A)
    B = set(range(1, m + 1))
    D = B - A
    if len(D) == 0:
        return m + 1
    else:
        return min(D)

Это решение имеет сложность O (N), и все угловые случаи учтены.

   public int solution(int[] A) {
        Arrays.sort(A);
        //find the first positive integer
        int i = 0, len = A.length;
        while (i < len && A[i++] < 1) ;
        --i;

        //Check if minimum value 1 is present
        if (A[i] != 1)
            return 1;

        //Find the missing element
        int j = 1;
        while (i < len - 1) {
            if (j == A[i + 1]) i++;
            else if (++j != A[i + 1])
                return j;
        }

        // If we have reached the end of array, then increment out value
        if (j == A[len - 1])
            j++;
        return j;
    }

Вот код на Python с комментариями, чтобы понять код - Кодируемость 100% отсутствующее целое число

Код-

def solution(A):
"""
solution at https://app.codility.com/demo/results/trainingV4KX2W-3KS/
100%
idea is to take temp array of max length of array items
for all positive use item of array as index and mark in tem array as 1 ie. present item
traverse again temp array if first found value in tem array is zero that index is the smallest positive integer
:param A:
:return:
"""
max_value = max(A)
if max_value < 1:
    # max is less than 1 ie. 1 is the smallest positive integer
    return 1
if len(A) == 1:
    # one element with 1 value
    if A[0] == 1:
        return 2
    # one element other than 1 value
    return 1
# take array of length max value
# this will work as set ie. using original array value as index for this array
temp_max_len_array = [0] * max_value
for i in range(len(A)):
    # do only for positive items
    if A[i] > 0:
        # check at index for the value in A
        if temp_max_len_array[A[i] - 1] != 1:
            # set that as 1
            temp_max_len_array[A[i] - 1] = 1
print(temp_max_len_array)
for i in range(len(temp_max_len_array)):
    # first zero ie. this index is the smallest positive integer
    if temp_max_len_array[i] == 0:
        return i + 1
# if no value found between 1 to max then last value should be smallest one
return i + 2


 arr = [2, 3, 6, 4, 1, 2]    
 result = solution(arr)

Это мое решение. Сначала мы начинаем с 1, мы перебираем массив и сравниваем с 2 элементами из массива, если он соответствует одному из элементов, которые мы увеличиваем на 1, и начинаем процесс заново.

private static int findSmallest(int max, int[] A) {

    if (A == null || A.length == 0)
        return max;

    for (int i = 0; i < A.length; i++) {
        if (i == A.length - 1) {
            if (max != A[i])
                return max;
            else
                return max + 1;
        } else if (!checkIfUnique(max, A[i], A[i + 1]))
            return findSmallest(max + 1, A);
    }
    return max;
}


private static boolean checkIfUnique(int number, int n1, int n2) {
    return number != n1 && number != n2;
}

Это мое решение, написанное на рубине, простое, правильное и эффективное

def solution(arr)

  sorted = arr.uniq.sort
  last = sorted.last
  return 1 unless last > 0

  i = 1
  sorted.each do |num|
    next unless num > 0
    return i unless num == i

    i += 1
  end
  i

end

Вот мое решение JavaScript, которое набрало 100% с O (N) или O (N * log (N)), обнаружив временную сложность:

function solution(A) {
    let tmpArr = new Array(1);

    for (const currNum of A) {
        if (currNum > arr.length) {
            tmpArr.length = currNum;
        }
        tmpArr[currNum - 1] = true;
    }

    return (tmpArr.findIndex((element) => element === undefined) + 1) || (tmpArr.length + 1);
}

Решение Java - Внутреннее решение метода

int N = A.length;

Set<Integer> set = new HashSet<>();
for (int a : A) {
    if (a > 0) {
        set.add(a);
    }
}

if (set.size()==0) {
    return N=1;
}

for (int i = 1; i <= N + 1; i++) {
    if (!set.contains(i)) {
        N= i;
        break;
    }
}
return N;

Решение на Scala со всеми запущенными тестами:

Class Solution {

  def smallestNumber(arrayOfNumbers: Array[Int]) = {
    val filteredSet = arrayOfNumbers.foldLeft(HashSet.empty[Int]){(acc, next) 
    => if (next > 0) acc.+(next) else acc}
    getSmallestNumber(filteredSet)

  }

  @tailrec
  private def getSmallestNumber(setOfNumbers: HashSet[Int], index: Int = 1): 
  Int = {
      setOfNumbers match {
        case emptySet if (emptySet.isEmpty) => index
        case set => if (!set.contains(index)) index else getSmallestNumber(set, 
          index + 1)
        }
      }

}

Мое простое и эффективное (по времени) решение для Java:

import java.util.*;

class Solution {
    public int solution(int[] A) {
        Set<Integer> set=new TreeSet<>();
        for (int x:A) {
            if (x>0) {
                set.add(x);
            }
        }

        int y=1;
        Iterator<Integer> it=set.iterator();
        while (it.hasNext()) {
            int curr=it.next();
            if (curr!=y) {
                return y;
            }
            y++;
        }
        return y;
    }
}

Пример Objective-C:

 int solution(NSMutableArray *array) {
     NSArray* sortedArray = [array sortedArrayUsingSelector: @selector(compare:)];
     int x = 1;
     for (NSNumber *number in sortedArray) {

       if (number.intValue < 0) {
         continue;
       }
       if (x < number.intValue){
         return x;
       }
      x = number.intValue + 1;
     }

     return x;
}

Я еще не видел решения C#, которое использует Linq ... вот самый простой способ (я думаю) пройти этот тест на 100%:

using System;
using System.Linq;

class Solution {
    public int solution(int[] A) => Enumerable.Range(1, 100001).Except(A).Min();
}

Тем не менее, я должен отметить, что, хотя приведенное выше является простым и дает 100% -ный результат теста, это не самый эффективный вариант. Для более эффективного решения Linq лучше подойдет что-то вроде следующего:

using System;
using System.Collections.Generic;

public static int solution(int[] A)
{
    var set = new HashSet<int>(A);

    return Enumerable.Range(1, A.Length + 1).First(i => !set.Contains(i));
}

Решение на JavaScript

function solution(A) {
    let smallestInt = 1;

    function existsInArray(val) {
        return A.find((a) => a === val);
    }

    for (let index = smallestInt; index < 1000000; index++) {
        if (existsInArray(index) && !existsInArray(index + 1) &&
            existsInArray(smallestInt)) {
            smallestInt = index + 1
        }
    }
    return smallestInt;
}

Этот ответ дает 100% на Python. Сложность наихудшего случая O (N).

Идея состоит в том, что нас не волнуют отрицательные числа в последовательности, поскольку мы хотим найти наименьшее положительное целое число, не входящее в последовательность A. Следовательно, мы можем установить все отрицательные числа в ноль и оставить только уникальные положительные значения. Затем мы итеративно проверяем, начиная с 1, входит ли число в набор положительных значений последовательности A.

Наихудший сценарий, когда последовательность представляет собой арифметическую прогрессию с постоянной разностью 1, приводит к повторению всех элементов и, следовательно, к сложности O (N).

В крайнем случае, когда все элементы последовательности отрицательны (т.е. максимум отрицателен), мы можем немедленно вернуть 1 как минимальное положительное число.

def solution(A):
    max_A=max(A)
    B=set([a if a>=0 else 0 for a in A ])
    b=1
    if max_A<=0:
        return(1)
    else:
        while b in B:
            b+=1
        return(b)

Вот простой и быстрый код в PHP.

• Оценка задачи: 100%
• Правильность: 100%
• Представление: 100%
• Обнаруженная временная сложность: O (N) или O (N * log (N))

function solution($A) {

    $x = 1;

    sort($A);

    foreach($A as $i){

        if ($i <=0) continue;

        if ($x < $i) return $x;

        else $x = $i+1; 

    }

    return $x;
}

Тесты производительности

Не лучший C++, но набрал 100% https://app.codility.com/demo/results/demoCNNMBE-B5W/

// you can use includes, for example:
#include <algorithm>
#include <iostream>

// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;

template <class T>
bool allneg(const T start, const T end) {
    T it;
    for (it = start; it != end; it++) {
        if (*it >= 0) return false;
    }

    return true;
}

int solution(vector<int> &A) {
    if (A.empty()) throw std::invalid_argument("unexpected empty vector");

    std::sort(A.begin(),A.end());
    /*
    for(size_t i = 0; i < A.size(); i++) {
        std::cout << A[i] << ", ";
    }*/
    if (allneg(A.begin(),A.end())){
        return 1;
    }
    int v = 1;
    auto it = A.begin();
    while(it!=A.end()){
        if (std::binary_search(it,A.end(),v)){
            v++;
        } else {
            return v;
        }
        it++;
    }
    return v;
}

На основе Самый быстрый способ найти наименьшее пропущенное целое число из списка целых чисел и немного быстрее, чем вышеупомянутый https://app.codility.com/demo/results/demoCJ7MDF-CDD/

int solution(vector<int> &A) {
    // write your code in C++14 (g++ 6.2.0)
    std::vector<bool> negative(1000000,false);
    std::vector<bool> non_negative(1000000+1,false);
    bool contain_negative = false;
    bool contain_non_negative = false;
    for(int a : A){
        if (a<0) {
            negative[-a] = true;
            contain_negative = true;
        } else {
            non_negative[a] = true;
            contain_non_negative = true;
        }
    }
    int result = 1;
    if (contain_negative && !contain_non_negative){
        return result;
    } else {
        for(size_t i = 1; i < non_negative.size(); i++){
            if (!non_negative[i]){
                result = i;
                break;
            }
        }
    }
    return result;
}

Swift с .reduce()

public func solution(_ A : inout [Int]) -> Int {
    return A.filter { $0 > 0 }.sorted().reduce(1) { $0 < $1 ? $0 : $1 + 1}
}

100% решение в Swift, я нашел его здесь, он действительно красивее, чем мой алгоритм ... Нет необходимости поворачивать массив как заказанный, вместо этого использовать словарь [Int: Bool] и просто проверять положительный элемент в словаре.

public func solution(_ A : inout [Int]) -> Int {
    var counter = [Int: Bool]()
    for i in A {
        counter[i] = true
    }

    var i = 1
    while true {
        if counter[i] == nil {
            return i
        } else {
            i += 1
        }
    }
}

Я попробовал это со Swift и получил 100%.

public func solution(_ A : inout [Int]) -> Int {
// write your code in Swift 4.2.1 (Linux)
if A.count == 0 {
    return 1
}
A = A.sorted()
if A[A.count - 1] <= 0 {
    return 1
}

var temp = 1

for numb in A {

    if numb > 0 {

        if numb == temp {
            temp += 1
        }else if numb != (temp - 1) {
            return temp
        }
    }
}

return temp

}

function solution(A = []) {
    return (A && A
        .filter(num => num > 0)
        .sort((a, b) => a - b)
        .reduce((acc, curr, idx, arr) => 
            !arr.includes(acc + 1) ? acc : curr, 0)
        ) + 1;
}

решение(); // 1 решение (ноль); // 1 решение([]); // 1 решение ([0, 0, 0]); // 1

Мое решение на Ruby

def solution(a)
  p = {}
  b = 1
  a.each do |n|
    p[n] = n
    b = n if n > b
  end

  nb = b
  (b-1).downto(1) do |n|
    unless p[n]
      nb = n
      break
    end
  end  
  (nb == b) ? b+1 : nb
end

puts solution([1,3,5,4,1,2,6])
puts solution([1,3,6,4,1,2,5])
puts solution([1,2,3])

JS:

• filter для получения положительных ненулевых чисел из массива
• sort над отфильтрованным массивом в порядке возрастания
• map для повторения цикла выше сохраненного результата
  • if, чтобы проверить, что x меньше текущего элемента, затем верните
  • в противном случае добавьте 1 в текущий элемент и назначьте x

function solution(A) {

    let x = 1
    
    A.filter(x => x >= 1)
     .sort((a, b) => a - b)
     .map((val, i, arr) => {
        if (x < arr[i]) return
        x = arr[i] + 1
    })

    return x
}

console.info(solution([3, 4, -1, 1]));
console.info(solution([1, 2, 0]));

Приведенный ниже код будет работать за время O (N) и сложность пространства O (N). Проверьте эту ссылку почтительность для полного текущего отчета.

Программа сначала помещает все значения в HashMap, находя максимальное число в массиве. Причина этого заключается в том, чтобы иметь только уникальные значения в предоставленном массиве, а затем проверять их в постоянное время. После этого другой цикл будет выполняться до максимального найденного числа и вернет первое целое число, которого нет в массиве.

   static int solution(int[] A) {
      int max = -1;
      HashMap<Integer, Boolean> dict = new HashMap<>();
      for(int a : A) {
         if (dict.get(a) == null) {
            dict.put(a, Boolean.TRUE);
         }
         if (max<a) {
            max = a;
         }
      }
      for(int i = 1; i<max; i++) {
         if (dict.get(i) == null) {
            return i;
         }
      }
      return max>0 ? max+1 : 1;
   }

Приведенный ниже код проще, но моим мотивом было написать для пользователей JavaScript, ES6:

function solution(A) {
   
    let s = A.sort();
    let max = s[s.length-1];
    let r = 1;
   
    // here if we have an array with [1,2,3] it should print 4 for us so I added max + 2
    for(let i=1; i <= (max + 2); i++) {
        r  = A.includes(i) ? 1 : i ;
        if (r>1) break;
    }
   
    return r;
}

Мое решение на Java получило 100%. Я считаю, что это просто, а сложность - O (n).

public int solution(int[] A) {
    Integer s = 1;
    List<Integer> list = new ArrayList<>();

    for (int i : A) {
        if (i>0) {
            list.add(i);
        }
    }

    Collections.sort(list);

    for (int i : list) {
        if (s < i) {
            return s;
        }
        s = i + 1;
    }

    return s;
}

Дайте мне знать, если мы сможем это улучшить.

Это решение на Javascript, но завершите тест со 100% результатом и меньшим количеством кодов.

function solution(A) {
    let s = A.sort((a, b) => { return a - b })
    let x = s.find(o => !s.includes(o+1) && o>0)
    return ((x<0) || !s.includes(1)) ? 1 : x+1
}

в C#

static int solutionA(int[] A)
    {
        Array.Sort(A);

        int minNumber = 1;

        if (A.Max() < 0)
        {
            return minNumber;
        }

        for (int i = 0; i < A.Length; i++)
        {
            if (A[i] == minNumber)
            {
                minNumber++;
            }
            
            if (A[i] > minNumber)
            {
                break;
            }
        }

        return minNumber;
    }

100% тест пройденhttps://i.stack.imgur.com/FvPR8.png

В PHP я могу добиться этого с помощью нескольких строк кода.

function solution($A) {
  for($i=1; in_array($i,$A); $i++);
  return $i;    
}

Версия Быстрый с использованием функций, а не итеративного подхода

«Решение получило высший балл» - Codility

В этом решении используются функции, а не итерационный подход. Таким образом, решение сильно зависит от оптимизации языка. Аналогичный подход может быть реализован в Ява, например, с использованием операций набора Java и других функций.

public func solution(_ A : inout [Int]) -> Int {
    let positives = A.filter{ $0 > 0}
    let max = positives.count <= 100_000 ? positives.count + 1 : 100_001
    return Set(1...max).subtracting(A).min() ?? -1
}

1. Получены все положительные числа из исходного массива.
2. Получены все возможные результаты на основании положительного подсчета. Ограничил набор до 100к, как указано в проблеме. Добавлен 1, если исходный массив был полной последовательностью.
3. Возвращено минимальное положительное число после исключения исходного массива элементы из множества всех возможных результатов.

Примечание: объявление функции было от Codility, и inout не нужен. Возврат целого числа не допускал nil, поэтому использовалось -1.

Перепишите принятый ответ с помощью Swift. Hashset в Swift - это Set. Я думаю, что если в качестве возвращаемого значения требуется индекс, попробуйте вместо этого использовать Dictionary.

Пройдено со 100% результатом.

public func solution(_ A: [Int]) -> Int {
    let n = A.count
    var aSet = Set<Int>()
    
    for a in A {
        if a > 0 {
            aSet.insert(a)
        }
    }
    
    for i in 1...n+1 {
        if !aSet.contains(i) {
            return i
        }
    }
    
    return 1
}

Приведенное ниже решение C++ получило 100% оценку. Теоретическая сложность кода составляет. Сложность времени: O (N) амортизируется из-за хеш-набора и сложности вспомогательного пространства O (N) из-за использования хэша для поиска за время O (1).

#include<iostream>
#include<string>
#include<vector>
#include<climits>
#include<cmath>
#include<unordered_set>

using namespace std;

int solution(vector<int>& A)
{
  if (!A.size())
    return(1);

  unordered_set<int> hashSet;
  int maxItem=INT_MIN;
  for(const auto& item : A)
  {
    hashSet.insert(item);
    if (maxItem<item)
      maxItem=item;
  }

  if (maxItem<1)
    return(1);

  for(int i=1;i<=maxItem;++i)
  {
    if (hashSet.find(i)==hashSet.end())
      return(i);
  }
  return(maxItem+1);
}

Вы можете просто использовать это, что является вариантом сортировки вставкой, без необходимости Set или сортировки всего массива.

    public static int solution(int[] A) {
    //we can choose only positive integers to enhance performance
        A = Arrays.stream(A).filter(i -> i > 0).toArray();
        for(int i=1; i<A.length; i++){
            int v1 = A[i];
            int j = i-1;
            while (j > -1 && A[j] > v1) {
                A[j + 1] = A[j];
                j = j - 1;
            }
            A[j + 1] = v1;
            if (A[i] - A[i-1] > 1){
                return A[i] + 1;
            }
        }
        return 1;
    }

Сначала позвольте мне объяснить алгоритм ниже. Если массив не содержит элементов, верните 1, Затем в цикле проверьте, больше ли текущий элемент массива, чем предыдущий элемент, на 2, тогда есть первое наименьшее отсутствующее целое число, верните его. Если текущий элемент следует за предыдущим элементом, то текущее наименьшее отсутствующее целое число является текущим целым числом + 1.

    Array.sort(A);

    if (A.Length == 0) return 1;

    int last = (A[0] < 1) ? 0 : A[0];

    for (int i = 0; i < A.Length; i++)
    {
        if (A[i] > 0){
            if (A[i] - last > 1) return last + 1;
            else last = A[i];
        } 
    }

    return last + 1;

Без сортировки и лишней памяти. Сложность времени: O (N)

  public int solution(int[] A) {
        for (int i = 0; i < A.length; i++) {
            if (A[i] <= 0 || A[i] >= A.length) continue;
            int cur = A[i], point;
            while (cur > 0 && cur <= A.length && A[cur - 1] != cur) {
                point = A[cur - 1];
                A[cur - 1] = cur;
                cur = point;
                if (cur < 0 || cur >= A.length) break;
            }
        }
        for (int i = 0; i < A.length; i++) {
            if (A[i] != i+1) return i+1;
        }
        return A.length + 1;
    }

Мое решение на Python 100% правильность

def solution(A):

  if max(A) < 1:
    return 1

  if len(A) == 1 and A[0] != 1:
    return 1

  s = set()
  for a in A:
    if a > 0:
      s.add(a)
  
  
  for i in range(1, len(A)):
    if i not in s:
      return i

  return len(s) + 1

assert solution([1, 3, 6, 4, 1, 2]) == 5
assert solution([1, 2, 3]) == 4
assert solution([-1, -3]) == 1
assert solution([-3,1,2]) == 3
assert solution([1000]) == 1

Это моя реализация в Swift 4 со 100% оценкой. Это должен быть очень похожий код на Java. Дайте мне знать, что вы думаете.

public func solution(_ A : inout [Int]) -> Int {
  let B = A.filter({ element in
    element > 0
  }).sorted()

  var result = 1
  for element in B {
    if element == result {
      result = result + 1
    } else if element > result {
      break
    }
  }

  return result
}

Ниже мое решение

int[] A = {1,2,3};
Arrays.sort(A);
Set<Integer> positiveSet = new HashSet<>();
for(int a: A) {
    if (a>0) {
        positiveSet.add(a);
    }
}
for(int a: A) {
    int res = a+1;
    if (!positiveSet.contains(res)) {
        System.out.println("result : "+res);
        break;
    }
}

Решение JavaScript без сортировки, 100% баллов и времени выполнения O (N). Он строит хэш-набор положительных чисел при нахождении максимального числа.

function solution(A) {
    set = new Set()
    let max = 0
    for (let i=0; i<A.length; i++) {
        if (A[i] > 0) {
            set.add(A[i])
            max = Math.max(max, A[i])
        }
    }

    for (let i=1; i<max; i++) {
        if (!set.has(i)) {
            return i
        }
    }
    return max+1
}

Это решение на C#:

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 = A.Length;
HashSet<int> set =new HashSet<int>();
foreach (int a in A) {
if (a > 0) {
    set.Add(a);
    }
}
for (int i = 1; i <= N + 1; i++) {
if (!set.Contains(i)) {
    return i;
    }
}
return N;
}
}

Я подумал, что простой способ сделать это - использовать BitSet.

• просто добавьте все положительные числа в BitSet.
• по завершении вернуть индекс первого бита очистки после бита 0.

public static int find(int[] arr) {
    BitSet b = new BitSet();
    for (int i : arr) {
        if (i > 0) {
            b.set(i);
        }
    }
    return b.nextClearBit(1);
}

Решение C#:

    public int solution(int[] A)
    {
        int result = 1;

        // write your code in Java SE 8
        foreach(int num in A)
        {
            if (num == result)
               result++;

            while (A.Contains(result))
                result++;
        }

        return result;
    }

Я думал о другом подходе (JS, JavaScript) и получил результат, который набрал 66% из-за проблем с производительностью:

    const properSet = A.filter((item) => { return item > 0 });
    let biggestOutsideOfArray = Math.max(...properSet);
    
    if (biggestOutsideOfArray === -Infinity) {
       biggestOutsideOfArray = 1;
    } else {
        biggestOutsideOfArray += 1;
    }
    
   for (let i = 1; i <= biggestOutsideOfArray; i++) {
       if (properSet.includes(i) === false) {
           return i;
       }
   } 
}

Как насчет того, чтобы просто поиграть с петлями.

import java.util.Arrays;
public class SmallestPositiveNumber {

    public int solution(int[] A) {
        Arrays.sort(A);
        int SPI = 1;

        if (A.length <= 1) return SPI;

        for(int i=0; i<A.length-1; i++){

            if ((A[i+1] - A[i]) > 1)
            {
                return A[i] + 1;
            }
        }
        return A[A.length-1]+1;
    }
}

Вот мое решение на Java:

public int solution(int[] A) {

   int smallestPositiveInteger = 1;
        
   Arrays.sort(A);

   if (A[0] <= 0) return smallestPositiveInteger;

      for( int i = 0; i < A.length; i++){
          if (A[i] == smallestPositiveInteger)
            smallestPositiveInteger++;
      }    

      return smallestPositiveInteger;
}

Со 100% точностью кодирования в Java

    public int solution(int[] A) {
        // write your code in Java SE 8

     Arrays.sort(A);
    int i=1;
    for (int i1 = 0; i1 < A.length; i1++) {
      if (A[i1] > 0 && i < A[i1]) {
        return i;
      }else if (A[i1]==i){
         ++i;
      }

    }
    return i;
    }

Кратчайший ответ на Python. 100%

def solution(A):
   return min([x for x in range(1,len(A) + 2) if x not in set(sorted([x for x in A if x>0 ]))])

Мое решение Javascript. Получил 100%. Решение состоит в том, чтобы отсортировать массив и сравнить соседние элементы массива.

function solution(A) {
// write your code in JavaScript (Node.js 8.9.4)
  A.sort((a, b) => a - b);

  if (A[0] > 1 || A[A.length - 1] < 0 || A.length === 2) return 1;

  for (let i = 1; i < A.length - 1; ++i) {
    if (A[i] > 0 && (A[i + 1] - A[i]) > 1) {
        return A[i] + 1;
    }
  }

  return A[A.length - 1] + 1;
}

Решение JavaScript ES6:

function solution(A) {
  if (!A.includes(1)) return 1;
  return A.filter(a => a > 0)
    .sort((a, b) => a - b)
    .reduce((p, c) => c === p ? c + 1 : p, 1);
}
console.info(solution([1, 3, 6, 4, 1, 2]));
console.info(solution([1, 2, 3]));
console.info(solution([-1, -3]));
console.info(solution([4, 5, 6]));
console.info(solution([1, 2, 4]));

это мой код в Котлине:

private fun soluction(A: IntArray): Int {
   val N = A.size
   val counter = IntArray(N + 1)

   for (i in A)
       if (i in 1..N)
           counter[i]++
   
   for (i in 1 until N + 1)
       if (counter[i] == 0)
           return i
     
   return N + 1
}

100% в Swift с использованием рекурсивной функции. O (N) или O (N * log (N))

var promise = 1

public func solution(_ A : inout [Int]) -> Int {
    // write your code in Swift 4.2.1 (Linux)
    execute(A.sorted(), pos: 0)
    return promise

}

func execute(_ n:[Int], pos i:Int) {
    if n.count == i || n.count == 0 { return }
    if promise > 0 && n[i] > 0 && n[i]+1 < promise {
        promise = n[i] + 1
    } else if promise == n[i] {
        promise = n[i] + 1
    }
    execute(n, pos: i+1)
}

Это для C#, он использует запросы HashSet и Linq и имеет 100% балл по Codility.

     public int solution(int[] A)
    {
        var val = new HashSet<int>(A).Where(x => x >= 1).OrderBy((y) =>y).ToArray();
        var minval = 1;
        for (int i = 0; i < val.Length; i++)
        {
            if (minval < val[i])
            {
                return minval;
            }
            minval = val[i] + 1;
        }

        return minval;
    }

Решение в kotlin с использованием set.

Космическая сложность: O (N)
Временная сложность: O (N)

fun solutionUsingSet(A: IntArray): Int {
    val set = HashSet<Int>()
    A.forEach {
        if (it > 0) {
            set.add(it)
        }
    }
    // If input array has no positive numbers
    if (set.isEmpty()) {
        return 1
    }
    for (i in 1 until A.size + 1) {
        if (!set.contains(i)) {
            return i
        }
    }
    // If input array has all numbers from 1 to N occurring once
    return A.size + 1
}