Ответ 1

возвращает минимальное положительное целое число, которое не встречается в A.

Итак, в массиве с только одним элементом, если это число равно 1, вы должны вернуть 2. Если нет, вы должны вернуть 1.

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

Итак, например, если вы повторяете от 1 до Integer.MAX_VALUE включительно и возвращаете первое значение, которое не находится в данном массиве, это приведет к правильным ответам. Вам нужно выяснить, какие структуры данных использовать, чтобы ваше решение масштабировалось с O(n).

Ответ 2

Вот мой ответ, получил 100/100.

import java.util.HashSet;

class Solution {
    public int solution(int[] A) {
        int num = 1;
        HashSet<Integer> hset = new HashSet<Integer>();

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

         while (hset.contains(num)) {
                num++;
            }

        return num;
    }
}

Ответ 3

Вот мое решение, которое получает 100% и 100%:

class Solution {
    public int solution(int[] A) {
        int len = A.length;
        int [] buffer = new int[len];
        int min = Integer.MAX_VALUE;

        // Find min within the array for the positive integers
        for (int i = 0; i < len; i++) {
            if (min > A[i] && A[i] > 0) min = A[i];
        }

        // No positive integer? Return 1
        if (min == Integer.MAX_VALUE) return 1;

        // Fill additional buffer with positive integers restricting to valus from 1 to A.length
        for (int i = 0; i < len; i++) {
            if (A[i] > len) continue;
            if (A[i] < 1) continue;
            buffer[A[i] - 1] = A[i];
        }

        // Return result
        if (buffer[0] != 1) return 1;
        for (int i = 0; i < len; i++) {
            if (buffer[i] == 0) return i + 1;
        }
        return len + 1;
    }

}

Ответ 4

Я нашел лучшее и самое простое решение:

Анализ анализа кодимента:

Решение получило идеальный результат. Правильность 100%
Производительность 100%
Оценка задачи 100%

public int solution(int[] A) {
        // write your code in Java SE 8
        Arrays.sort(A);
        int y = 1;
        for (int i = 0; i < A.length; i++) {
            if (y < A[i]) {
                return y;
            }
            if (y == A[i])
                y++;
        }
        return y;
    }

Ответ 5

Вот простой ответ:

import java.util.*;

class Solution {
    public int solution(int[] A) {
        Arrays.sort(A);
        int minValue = 1;
        for(int value: A){
            if (value == minValue){
                minValue++;
            }
        }
        return minValue;
    }
}

Ответ 6

Я сделал ответ, основанный на ответе Denes, но более простой.

int counter[] = new int[A.length];

// Count the items, only the positive numbers
for (int i = 0; i < A.length; i++)
    if (A[i] > 0 && A[i] <= A.length)
        counter[A[i] - 1]++;

// Return the first number that has count 0
for (int i = 0; i < counter.length; i++)
    if (counter[i] == 0)
        return i + 1;

// If no number has count 0, then that means all number in the sequence
// appears so the next number not appearing is in next number after the
// sequence.
return A.length + 1;

Ответ 7

Здесь мое решение, которое получило 100/100.

public int solution(int[] A) {
    int len = 100000;
    if (A.length < len) {
        len = A.length;
    }
    int[] r = new int[len];
    Arrays.fill(r, 0);
    for (int i = 0; i < len; i++) {
        if (Integer.signum(A[i]) > 0 && A[i] <= len) {
            int x = A[i];
            r[x - 1] = 1;
        }
    }

    for (int j = 0; j < len; j++) {
        if (r[j] == 0) {
            return j + 1;
        }
    }
    return A.length + 1;
}

Ответ 8

Получил 100% с этим в С#

public int solution(int[] A) {
    // write your code in C# 6.0 with .NET 4.5 (Mono)

    var testArray = new HashSet<int>(A);
    int minNum = 1;

    while(testArray.Contains(minNum)) minNum++;

    return minNum;
}

Ответ 9

Вот мое решение, использующее TreeSet: Test Score: 100%

import java.util.*;

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

    TreeSet<Integer> ts = new TreeSet<>();  
    for (int i=0; i<A.length; i++)
        if(A[i]>0) ts.add(A[i]);

    Iterator<Integer> it = ts.iterator();
    int i = 1;
    if(!it.hasNext()) return i;
    while(it.hasNext()){
        if(it.next() != i++) {
        i--;
        break;
        }
    }

    return i;

    }
}

Ответ 10

это получило 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);
}

Ответ 11

O (n) время и пространство, я думаю, что return -1 недостижима (если они не изменяют req. для поддержки N = 1000000 > _ <

    Set<Integer> hash = new HashSet<Integer>();

    for(int num : A){
        hash.add(num);    
    }

    for(int i=1;i<1000000;i++){
        if(!hash.contains(i)){
            return i;
        }
    }

    return -1;
}

Ответ 12

88% в производительности и 100% тестовых случаев:

public int solution(int[] A) {      

    Integer[] b= Arrays.stream(A).boxed().toArray(Integer[]::new);

    HashSet<Integer> set = new HashSet<Integer>();      
    set.addAll(Arrays.asList(b));

    int i = 1;
    for (; i <= set.size(); i++) {
        if(set.contains(i))
            continue;
        else
            return i;
    }       
    return i;

}

Ответ 13

возвращает минимальное положительное целое число, которое не встречается в A

Ключ здесь состоит в том, что ноль не включен в вышеприведенное (поскольку это не положительное целое число). Таким образом, функция никогда не должна возвращаться 0. Я считаю, что это охватывает оба ваших неудачных случая выше.

edit: из-за того, что вопрос был изменен, так как это было написано, этот ответ больше не имеет отношения к делу

Ответ 14

Очень мало неправильно. Просто последняя строка

return 1;

должен прочесть

return A.length + 1;

потому что в этот момент вы нашли и удалили ВСЕ КЛЮЧИ от 1 до A.length, поскольку у вас есть записи массива, соответствующие каждому из них. Тест требует, чтобы в этой ситуации вы возвращали следующее целое число, превышающее наибольшее значение, найденное в массиве A. Все другие возможные случаи (например, отрицательные записи, пропущенное 1, пропущенное число в диапазоне от 1 до A.length) покрываются путем возврата первого неустранимого ключа. найдено под итерацией. Итерация здесь выполняется "естественным порядком", т.е. 1.. max, по умолчанию для TreeMap. Таким образом, первый не удаленный ключ будет самым маленьким отсутствующим целым числом.

Это изменение должно сделать 2 неправильных теста снова в порядке. Так что 50/50 за правильность.

Эффективность, конечно, другое дело. Использование здесь структуры данных TreeMap приводит к потере времени при оценке результатов теста. Более простые структуры данных (которые по существу используют ваш алгоритм) будут быстрее.

Этот более примитивный алгоритм избегает сортировки и копирует все записи> 1 в новый массив длиной 100001, так что индекс x содержит значение x. На самом деле он работает быстрее, чем код Сердара со средними и большими входными массивами.

public int solution(int[] A) 
{
    int i = 0,
        count = 0,
        N = A.length;
    int[] B = new int[100001];      // Initially all entries are zero

    for (i = 0; i < N; i++)         // Copy all entries > 0 into array B ...
        if (A[i] > 0 && A[i] < 100001)
        {
            B[A[i]] = A[i];         // ... putting value x at index x in B ...
            count++;                // ... and keep a count of positives
        }

    for (i = 1; i < count + 1; i++) // Find first empty element in B 
        if (B[i] == 0)              
            return i;               // Index of empty element = missing int 

                                    // No unfilled B elements above index 0 ? 
    return count + 1;               // => return int above highest filled element
}

Ответ 15

https://codility.com/demo/results/demoEHFE2K-SZ3/

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

import java.util.Arrays;

class Solution {
    public int solution(int[] a) {
        int min = 1;
        Arrays.sort(a);

        for (int i : a) {
            if (i > -1 && i == min) {
                    min++;
            }
        }

        return min;

    }
}

Ответ 16

Решение с усложнением пространства O (1) (лучше тогда требуется) Но у меня есть некоторые проблемы с производительностью (не понимаю, почему так, потому что бит-операции очень быстрые. Должно быть так)

private bool IsBitSet(int map, int pos)
        {
            return (map & (1 << pos)) != 0;
        }


        private int SetBit(int map, int bitPosition)
        {
            int m;
            m = 1 << bitPosition;
            map = map | m;
            return map;
        }


        public int solution(int[] A)
        {
            if (A.Length > 100000) return -1;
            if (A.Length == 0) return -1;


            int bitMap = 0;
            for (var i = 0; i < A.Length; i++)
            {
                if (A[i] > 0)
                {
                    bitMap = SetBit(bitMap, A[i]);
                }
            }

            int j = 1;
            while (IsBitSet(bitMap, j))
            {
                j++;
            }

            if (j > 0)
                return j;

            return -1;

        }

Ответ 17

Это набрало 100/100.

import java.util.*;

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

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

        for(int x:A) {
            set.add(x);
        } 

        int maximum = Collections.max(set);

        while (maximum <= 0) {
            maximum ++;
        }

        int num = maximum + 1;

        for(int i=1; i<=maximum; i++) {
            num = i;
            if(set.contains(num)) {
                num++;
            }
            else {
                break;
            }
        }
        return num;
    }
}

Ответ 18

Получите 100% с помощью этого простого кода https://codility.com/demo/results/training6HFRME-FZQ/

import java.util.Set;
import java.util.HashSet;
import java.util.Iterator;

class Solution {
 public int solution(int[] A) {
    // write your code in Java SE 8
    if(A.length>=1)
    {
    Set<Integer> hs=new HashSet<Integer>();
    for(int i=0;i<A.length;i++)
    {
        if(A[i]>0) 
        {
            hs.add(A[i]);
        }
    }
    //System.out.println("Hashset: "+hs);
    int num=1;
    while (hs.contains(num)) 
    {
            num++;
    }
    return num;
    }
  return 0;
  }
}

Ответ 19

Раствор В C: 100% https://codility.com/demo/results/training9VHK6V-2N3/

#include <string.h>

int solution(int A[], int N) {
    // write your code in C99 (gcc 6.2.0)
    int B[N];

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

    return N+1; 
}

Ответ 20

Здесь мое решение Java8. 100%/100%

import java.util.HashSet;

public class PermCheck {

    public int solution(int[] A) {
        if (A.length == 0) return 1;
        if (A.length == 1) { 
            if (A[0] == 1)
                return 1;
            else
                return 0;
        }
        int num = 1;
        int sumA = 0;
        int sumB = 0;
        HashSet<Integer> hs = new HashSet<>();
        for (int i : A) {
            if (i < 1) return 0;
            if (i > A.length) return 0; //not permutation
            if (hs.contains(i)) return 0;
            hs.add(i);
            sumA += i;
            sumB += num;
            num++;
        }
        return sumA == sumB ? 1 : 0;
    }
}

Ответ 21

Здесь очень простое решение c++, которое оценивает 100% и самоочевидно.

#include<algorithm>

int solution(vector<int> &A) {
    int i,n,max;

    n=A.size();

    /* Choose the new vector, size as of max element and put values as 0 */
    vector<int>v;
    max = *max_element(A.begin(),A.end());

    for(i=0;i<=max;++i)
        v.push_back(0);

    /* For each value increase the value at that index by 1 */
    for(i=0;i<n;++i){
        if(A[i]>0)
             v[A[i]]+=1;
    }

    /* Now simply check if new vector value is zero, that mean number
       with that index not exist */
    for(i=1;i<=max;++i){
        if(v[i]==0)
            break;
    }

    return i;
}

Ответ 22

работает хорошо!

public class Solution {

int n =1;

public int solution(int[] A) {

    if(A == null || A.length == 0){
        return 1;
    }

    int index = 0;

    for (int i = 0; i < A.length; i++) {
         if(n == A[i]){
            n++;
        }
        else if(n < A[i] && A.length > 1){
            swap(A, i, index );
            index++;
        }
    }

    if(index > 0){
        int []tmp = new int[index];
        for (int i = 0; i < index; i++) {
            tmp[i] = A[i];
        }
        return solution(tmp);
    }
    else{
        return n;
    }
}


private void swap(int[] A, int i, int j) {
    int tmp=A[i];
    A[i] = A[j];
    A[j] = tmp;
}

}

Ответ 23

Получил 100/100

int solution(int[] A) {
    //Maximum number
    final int N = 1_000_000;
    //Create an array in which we store the existence of the given number
    boolean[] barr = new boolean[N];
    //Conduct mapping. Ignore negative numbers
    for (int i : A) {
        if (i > 0) {
            barr[i - 1] = true;
        }
    }
    //Find the result
    for (int b = 0; b < barr.length; b++) {
        if (!barr[b]) return b + 1;
    }
    //If we got here, it means initial array contains all numbers 1..N
    return N + 1;
}

Ответ 24

Для тех, кто интересуется Python, работает 100/100:

def solution(A):
    min = 1
    A.sort()
    for i in A:
        if (i > - 1 and i == min):
            min  = min +1
    return min

Ответ 25

Оценка: - 100/100 - Простой и сладкий! Сложность времени O (n) и пространство O (n) -

public int solution(int[] A) {
    int min = 1;
    if(A.length == 0) {
        return min;
    }

    Set<Integer> set = new HashSet<>();
    for(int i = 0; i < A.length; i++) {
        set.add(A[i]);
    }

    for(int i = 1; i <= set.size(); i++) {
        if(set.contains(i)) {
            min = i;
            continue;
        } else {
            return i;
        }
    }

    return min + 1;
}

Ответ 26

Мое решение python - получило 100 в правильности и эффективности и работает в O (n) времени и пространстве

def solution(A):
    for i in range(1,max(A)+2):
        if i not in set(A):
            return i
    return 1

Ответ 27

Решение с использованием наборов с предварительным преобразованием из int в Integer в O (n)

import java.util.*;
class Solution {
  public int solution(int[] A) {
    Set<Integer> mySet = new HashSet<Integer>(Arrays.asList(Arrays.stream( A ).boxed().toArray( Integer[]::new )));
    Integer ret = 1;   
    while (mySet.contains(ret))
        ret++;
    return ret;
  }
}

Ответ 28

Решение Ruby и получило 100/100

def solution(a)
    min = 1
    a.sort!
    a.each do |i|
        if (i > - 1 and i == min)           
            min  = min +1 #5
        end
    end

    return min
end

Ответ 29

def Генератор():   = 0   в то время как (True):       I + 1 =       выход i

г = генератор()

def solution (ar):   s = set ([x для x в ar, если x > 0])   для я in s:       c = next (g)       если c!= i:           return c   return next (g)