Отсутствует целочисленная вариация - требуется решение O (n)

Ответ 1

В принципе pigeonhole по крайней мере одно из чисел 1, 2,..., n + 1 не находится в массиве. Создадим булевой массив b размера n + 1, чтобы сохранить, присутствует ли каждое из этих чисел.

Теперь мы обрабатываем входной массив. Если мы найдем число от 1 до n + 1, отметьте соответствующую запись в b. Если число, которое мы видим, не вписывается в эти границы, просто отбросьте его и перейдите к следующему. Оба случая: O (1) на входную запись, общее O (n).

После того, как мы закончим обработку ввода, мы можем найти первую не отмеченную запись в нашем булевом массиве b тривиально в O (n).

Ответ 2

Создайте хэш-таблицу всех значений. Для чисел от 1 до n + 1 проверьте, находятся ли они в хеш-таблице. По крайней мере один из них - нет. Распечатайте самый низкий номер.

Это O (n) ожидаемое время (вы можете получить с высокой вероятностью). См. Ответ @Gassa о том, как избежать хэш-таблицы в пользу таблицы поиска размера O (n).

Ответ 3

написал это сегодня и получил 100/100. не самое изящное решение, но легко понять -

public int solution(int[] A) {
    int max = A.length;
    int threshold = 1;
    boolean[] bitmap = new boolean[max + 1];

    //populate bitmap and also find highest positive int in input list.
    for (int i = 0; i < A.length; i++) {
        if (A[i] > 0 && A[i] <= max) {
            bitmap[A[i]] = true;
        }

        if (A[i] > threshold) {
            threshold = A[i];
        }
    }

    //find the first positive number in bitmap that is false.
    for (int i = 1; i < bitmap.length; i++) {
        if (!bitmap[i]) {
            return i;
        }
    }

    //this is to handle the case when input array is not missing any element.
    return (threshold+1);
}

Ответ 4

public int solutionMissingInteger(int[] A) {
    int solution = 1;
    HashSet<Integer> hashSet = new HashSet<>();

    for(int i=0; i<A.length; ++i){
        if(A[i]<1) continue;
        if(hashSet.add(A[i])){
            //this int was not handled before
            while(hashSet.contains(solution)){
                solution++;
            }
        }
    }

    return solution;
}

Ответ 5

С# набрал 100%,

Объяснение: использование таблицы поиска, в которой мы храним уже увиденные значения из входного массива, мы заботимся только о значениях, которые больше 0 и ниже или равно длины на входном массиве

    public static int solution(int[] A)
    {
        var lookUpArray = new bool[A.Length];

        for (int i = 0; i < A.Length; i++)
            if (A[i] > 0 && A[i] <= A.Length)
                lookUpArray[A[i] - 1] = true;

        for (int i = 0; i < lookUpArray.Length; i++)
            if (!lookUpArray[i])
                return i + 1;

        return A.Length + 1;
    }

Ответ 6

100% Javascript

function solution(A) {
        // write your code in JavaScript (Node.js 4.0.0)
        var max = 0;
        var array = [];
        for (var i = 0; i < A.length; i++) {
            if (A[i] > 0) {
                if (A[i] > max) {
                    max = A[i];
                }
                array[A[i]] = 0;
            }
        }
        var min = max;
        if (max < 1) {
            return 1;
        }
        for (var j = 1; j < max; j++) {
            if (typeof array[j] === 'undefined') {
                return j
            }
        }
        if (min === max) {
            return max + 1;
        }
    }

Ответ 7

Простой Java-интерфейс. Скорректировано 100/100 в правильности и производительности.

public int solution(int[] A) {
    int smallestMissingInteger = 1;
    if (A.length == 0) {
        return smallestMissingInteger;
    }
    Set<Integer> set = new HashSet<Integer>();
    for (int i = 0; i < A.length; i++) {
        if (A[i] > 0) {
            set.add(A[i]);
        }
    }
    while (set.contains(smallestMissingInteger)) {
        smallestMissingInteger++;
    }
    return smallestMissingInteger;

}

Ответ 8

Я считаю, что решение более активно, чем "маркировка" соответствующих значений с использованием булевого массива из n (100 000) элементов. Булевский массив размера n не будет "непосредственно" отображать возможный диапазон значений (-2,147,483,648 до 2,147,483,647). В этом примере Java я написал попытки сопоставить строки 100K путем сопоставления значения на основе их смещения от максимального значения. Он также выполняет модуль, чтобы уменьшить результирующий массив до того же размера, что и длина элемента элемента.

/** 
 * 
 * This algorithm calculates the values from the min value and mods this offset with the size of the 100K sample size. 
 * This routine performs 3 scans. 
 * 1. Find the min/max
 * 2. Record the offsets for the positive integers
 * 3. Scan the offsets to find missing value.
 * 
 * @author Paul Goddard
 *
 */
public class SmallestPositiveIntMissing {
    static int ARRAY_SIZE = 100000;
    public static int solve(int[] array) {
        int answer = -1;
        Maxmin maxmin = getMaxmin(array);
        int range = maxmin.max - maxmin.min;
        System.out.println("min:   " + maxmin.min);
        System.out.println("max:   " + maxmin.max);
        System.out.println("range: " + range);
        Integer[] values = new Integer[ARRAY_SIZE];
        if (range == ARRAY_SIZE) {
            System.out.println("No gaps");
            return maxmin.max + 1;
        }
        for (int val: array) {
            if (val > 0) {
                int offset = val - maxmin.min;
                int index = offset % ARRAY_SIZE;
                values[index] = val;
            } 
        }
        for (int i = 0; i < ARRAY_SIZE; i++) {
            if (values[i] == null) {
                int missing = maxmin.min + i;
                System.out.println("Missing: " + missing);
                answer = missing;
                break;
            }
        }
        return answer;
    }

    public static Maxmin getMaxmin(int[] array) {
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        for (int val:array) {
            if (val >=0) {
                if (val > max) max = val;
                if (val < min) min = val;
            }
        }
        return new Maxmin(max,min);
    }

    public static void main(String[] args) {
        int[] A = arrayBuilder();
        System.out.println("Min not in array: " + solve(A));
    }

    public static int[] arrayBuilder() {

        int[] array = new int[ARRAY_SIZE];
        Random random = new Random();

        System.out.println("array: ");
        for (int i=0;i < ARRAY_SIZE; i++) {
            array[i] = random.nextInt();
            System.out.print(array[i] + ", ");
        }
        System.out.println(" array done.");

        return array;
    }

}
class Maxmin {
    int max;
    int min;
    Maxmin(int max, int min) {
        this.max = max;
        this.min = min;
    }
}

Ответ 9

Это сработало для меня. Это не O (n), но немного проще:

import java.util.stream.*;
class Solution {
    public int solution(int[] A) {
        A = IntStream.of(A)
            .filter(x->x>0)
            .distinct()
            .sorted()
            .toArray();

        int min = 1;
        for(int val : A)
        {
            if(val==min)
                min++;
            else
                return min;
        }
        return min;
    }
}

Ответ 10

100%: процедура сортировки Python не рассматривается как обман...

def solution(A):
    """
    Sort the array then loop till the value is higher than expected
    """
    missing = 1
    for elem in sorted(A):
        if elem == missing:
            missing += 1
        if elem > missing:
            break
    return missing

Ответ 11

Версия Sweet Swift. 100% правильно

public func solution(inout A : [Int]) -> Int {
    //Create a Hash table
    var H = [Int:Bool]()
    // Create the minimum possible return value
    var high = 1
    //Iterate
    for i in 0..<A.count {
        // Get the highest element
        high = A[i] > high ? A[i] : high
        // Fill hash table
        if (A[i] > 0){
            H[A[i]] = true
        }
    }
    // iterate through possible values on the hash table
    for j in 1...high {
        // If you could not find it on the hash, return it
        if H[j] != true {
            return j
        } else {
            // If you went through all values on the hash
            // and can't find it, return the next higher value
            // e.g.: [1,2,3,4] returns 5
            if (j == high) {
                return high + 1
            }
        }
    }
    return high
}

Ответ 12

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

Ответ 13

javascript 100% 100% сначала сортируйте массив, вам просто нужно сканировать положительные элементы, так что найдите индекс 1 (если в массиве нет 1, тогда ответ равен 1). затем найдите элементы после 1, чтобы найти отсутствующий номер.

function solution(A) {
// write your code in JavaScript (Node.js 6.4.0)

   var missing = 1;
   // sort the array.
   A.sort(function(a, b){ return a-b });

   // try to find the 1 in sorted array if there is no 1 so answer is 1
   if ( A.indexOf(1) == -1) { return 1;}

   // just search positive numbers to find missing number 
   for ( i = A.indexOf(1); i < A.length; i++) {
      if ( A[i] != missing) {
        missing++;
        if ( A[i] != missing ) {return missing;}
      }
   }

   // if cant find any missing number return next integer number
   return missing+1;
}

Ответ 14

Простое решение 100%

public static int solution (final int [] A) {

Arrays.sort(A);

int min = 1;

// Starting from 1 (min), compare all elements, if it does not match 
//that would the missing number.
for (int i : A) {

  if (i == min) {
    min++;
  }

}

return min;

}

Ответ 15

Swift 3 - 100%

public func solution(_ A : inout [Int]) -> Int {
// write your code in Swift 3.0 (Linux)

var solution = 1
var hashSet = Set<Int>()

    for int in A
    {
        if int > 0
        {
            hashSet.insert(int)

            while hashSet.contains(solution)
            {
                solution += 1
            }
        }
    }

    return solution
}

Спасибо Мариану ответить выше.

Ответ 16

Это мое решение, использующее python:

def solution(A):
    m = max(A)

    if m <= 0:
        return 1

    if m == 1:
        return 2

    # Build a sorted list with all elements in A
    s = sorted(list(set(A)))

    b = 0

    # Iterate over the unique list trying to find integers not existing in A
    for i in xrange(len(s)):
        x = s[i]

        # If the current element is lte 0, just skip it
        if x <= 0:
            continue;

        b = b + 1

        # If the current element is not equal to the current position,
        # it means that the current position is missing from A
        if x != b:
            return b

    return m + 1

Scored 100%/100% https://codility.com/demo/results/demoDCU7CA-SBR/

Ответ 17

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>

int solution(int A[], int N) {
    // write your code in C99 (gcc 6.2.0)
    int i;
    bool *bin = (bool *)calloc((N+1),sizeof(bool));

    for (i = 0; i < N; i++)
    {
        if (A[i] > 0 && A[i] < N+1)
        {
            bin[A[i]] = true;
        }
    }

    for (i = 1; i < N+1; i++)
    {
        if (bin[i] == false)
        {
            break;
        }
    }

    return i;
}

Ответ 18

Это мое решение - Swift 4

public func solution(_ A: inout [Int]) -> Int {

    var minNum = 1
    var hashSet = Set<Int>()

    for int in A {
        if int > 0 {
            hashSet.insert(int)
        }
    }

    while hashSet.contains(minNum) {
        minNum += 1
    }

    return minNum

}

var array = [1,3,6]

solution(&array)

//Ответ: 2

Ответ 19

Код для C, на самом деле, это может использоваться для любого языка программирования без каких-либо изменений в логике.

Логика - это сумма N число N*(N+1)/2.

int solution(int A[], int N) {

    // write your code in C99
    long long sum=0;
    long long i;
    long long Nsum=0;

    for(i=0;i<N;i++){
        sum=sum + (long long)A[i];
    }

    if (N%2==0){
        Nsum= (N+1)*((N+2)/2);
        return (int)(Nsum-sum);
    }
    else{
        Nsum= ((N+1)/2)*(N+2);
        return (int)(Nsum-sum);
    }    

}

Это дало оценку 100/100.

Ответ 20

Это решение получает 100/100 от теста:

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

        int x = 0;
        while (x < A.length) {
            // Keep swapping the values into the matching array positions.
            if (A[x] > 0 && A[x] <= A.length && A[A[x]-1] != A[x])  {
                swap(A, x, A[x] - 1);
            } else {
                x++; // Just need to increment when current element and position match.
            }
        }

        for (int y=0; y < A.length; y++) {
            // Find first element that doesn't match position.
            // Array is 0 based while numbers are 1 based.
            if (A[y] != y + 1)  {
                return y + 1;
            }
        }

        return A.length + 1;
    }

    private void swap (int[] a, int i, int j) {
        int t = a[i];
        a[i] = a[j];
        a[j] = t;
    }
}

Ответ 21

100% в PHP https://codility.com/demo/results/trainingKFXWKW-56V/

function solution($A){
    $A = array_unique($A);
    sort($A);
    if (empty($A)) return 1;
    if (max($A) <= 0) return 1;
    if (max($A) == 1) return 2;
    if (in_array(1, $A)) {
    $A = array_slice($A, array_search(1, $A)); // from 0 to the end
    array_unshift($A, 0); // Explanation 6a
    if ( max($A) == array_search(max($A), $A)) return max($A) + 1; // Explanation 6b
        for ($i = 1; $i <= count($A); $i++){
                if ($A[$i] != $i) return $i; // Explanation 6c
        }
    } else {
        return 1;
    }
}

//Объяснение

• удалить все дубликаты
• сортировать от min до max
• если массив пуст, возвращает 1
• если max массива равен нулю или меньше, return 1
• если max массива равно 1, return 2//следующее положительное целое
• все остальные случаи: 6a) разделить массив от значения 1 до конца и добавить 0 перед первым номером 6b), если значением последнего элемента массива является макс. Массива, тогда массив возрастает, поэтому мы возвращаем max + 1//следующее положительное целое число 6c), если массив не возрастает, мы обнаруживаем недостающее число функцией для: если ключ элемента не является значением элемента, но должен быть (A = [0 = > 0, 1 = > 1,2 = > 3,...]), мы возвращаем ключ, потому что мы ожидаем, что ключ и значение будут равны.

Ответ 22

Вот мое решение, оно дает 88% оценки - время равно O (n), правильность 100%, производительность 75%. ПОМНИТЕ - возможно иметь массив всех отрицательных чисел или чисел, которые превышают 100 000. Большинство из вышеперечисленных решений (с фактическим кодом) дают гораздо более низкие баллы или просто не работают. Другие, похоже, не имеют отношения к проблеме Missing Integer, представленной на Codility.

int compare( const void * arg1, const void * arg2 )
{
    return *((int*)arg1) - *((int*)arg2);
}

solution( int A[], int N )
{
    // Make a copy of the original array
    // So as not to disrupt it contents.
    int * A2 = (int*)malloc( sizeof(int) * N );
    memcpy( A2, A1, sizeof(int) * N );

    // Quick sort it.
    qsort( &A2[0], N, sizeof(int), compare );

    // Start out with a minimum of 1 (lowest positive number)
    int min = 1;
    int i = 0;

    // Skip past any negative or 0 numbers.
    while( (A2[i] < 0) && (i < N )
    {
        i++;
    }

    // A variable to tell if we found the current minimum
    int found;
    while( i < N )
    {
        // We have not yet found the current minimum
        found = 0;
        while( (A2[i] == min) && (i < N) )
        {
            // We have found the current minimum
            found = 1;
            // move past all in the array that are that minimum
            i++;
        }
        // If we are at the end of the array
        if( i == N )
        {
            // Increment min once more and get out.
            min++;
            break;
        }
        // If we found the current minimum in the array
        if( found == 1 )
        {
            // progress to the next minimum
            min++;
        }
        else
        {
            // We did not find the current minimum - it is missing
            // Get out - the current minimum is the missing one
            break;
        }
    }

    // Always free memory.
    free( A2 );
    return min;
}

Ответ 23

    static int spn(int[] array)
    {
        int returnValue = 1;
        int currentCandidate = 2147483647;

        foreach (int item in array)
        {
            if (item > 0)
            {
                if (item < currentCandidate)
                {
                    currentCandidate = item;
                }
                if (item <= returnValue)
                {
                    returnValue++;
                } 
            }
        }

        return returnValue;
    }

Ответ 24

Может быть полезно, я использую арифметическую прогрессию, чтобы вычислить сумму, и используя бинарное исследование, элемент извлекается. проверено с массивом из нескольких сотен значений, работает хорошо. Поскольку на шаге 2 есть один для цикла и атракции, O (n/2) или меньше

def Missingelement (A):
    B = [x for x in range(1,max(A)+1,1)]
    n1 = len(B) - 1
    begin = 0
    end = (n1)//2
    result = 0
    print(A)
    print(B)
    if (len(A) < len(B)):
        for i in range(2,n1,2):
            if BinSum(A,begin,end) > BinSum(B,begin,end) :
               end = (end + begin)//2
               if (end - begin) <= 1 :
                result=B[begin + 1 ]    
            elif BinSum(A,begin,end) == BinSum(B,begin,end):
                r = end - begin
                begin = end 
                end = (end + r)

            if begin == end :
                result=B[begin + 1 ]    
    return result         


def BinSum(C,begin,end):
    n = (end - begin)

    if end >= len(C): 
        end = len(C) - 1
    sum =  n*((C[begin]+C[end])/2)
    return sum                


def main():
    A=[1,2,3,5,6,7,9,10,11,12,14,15]
    print ("smallest number missing is ",Missingelement(A))
if __name__ == '__main__': main()