только 77% при тестировании образца codility - PullRequest
Новая
       49

только 77% при тестировании образца codility

0 голосов
/ 21 марта 2020

Я пробовал демонстрационный тест codility, но никогда не получал более 77% из-за их тестов производительности.

тест в основном утверждает: если массив A из N целых чисел, возвращает наименьшее положительное целое число (больше чем 0) что не встречается в A.

Что не так с моим решением?

Проведенный тест производительности показывает: ОШИБКА ВРЕМЕНИ: время выполнения: 0,152 се c., Ограничение по времени: 0,100 се c. 

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

class Solution3 {
    int solution(int[] A) {
        ArrayList<Integer> list = Arrays.stream(A).boxed().distinct().sorted()
                .filter(i -> i > 0)
                .collect(Collectors.toCollection(ArrayList::new));

        Integer prev_item = 0;

        for (int i = 0; i < list.size(); i++) {
            Integer item = list.get(i);

            if (!(item - 1 == prev_item)) {
                return prev_item + 1;
            }
            prev_item = item;
        }
        return prev_item + 1;
    }


    public static void main(String[] args) {
        Solution3 solution3 = new Solution3();
        int[] A = new int[6];
        A[0] = 1;
        A[1] = 2;
        A[2] = 3;
        A[3] = 8;
        A[4] = 8;
        A[5] = 11;

        int solution = solution3.solution(A);
        System.out.println("solution: " + solution);
    }
}

1 Ответ

0 голосов
/ 21 марта 2020

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

Было бы намного лучше с точки зрения производительности, если бы вы просто отсортируйте массив с помощью Arrays.sort(A), а затем выполните двоичный поиск по первому положительному значению и сделайте все остальное.

...