Ускорить код Java

Question

Как я могу ускорить работу данного метода, возможно есть части кода, которые я слишком сложно реализовал, есть более простой способ?

import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.stream.Collectors;
import java.util.stream.IntStream;


class Solution {
    public int firstMissingPositive(int[] nums) {
        List<Integer> positiveIntegerList = Arrays.stream(nums).distinct().filter(e -> e > 0).boxed().sorted(Comparator.naturalOrder()).collect(Collectors.toList());
        int end = positiveIntegerList.size();
        if(end == 0 || positiveIntegerList.get(0) != 1){
            return 1;
        }
        else if(positiveIntegerList.get(end-1) == end){
            return end + 1;
        }
        else{
            int start = 0;
            int middle_index;
            while (end >= start) {
                if (end - start <= 2){
                    for (int i = start;i <= end; i++){
                        if(positiveIntegerList.get(i) != i + 1){
                            return i + 1;
                        }
                    }
                    return positiveIntegerList.get(end) + 1;
                } 
                middle_index = (start + end) / 2;
                if(positiveIntegerList.get(middle_index) == middle_index + 1){
                    start = middle_index + 1;
                }
                else{
                    end = middle_index - 1;
                }
            }
        }
        return -1;
    }
}

Answer 1

Ваш алгоритм сортирует за O(NlogN), а затем выполняет двоичный поиск за O(logN). Оптимизировать поиск бесполезно, время уже упущено во время сортировки.

"Отсортировать" массив можно за линейное время. Кавычки потому что это не сортировка как таковая. Нужно так переставить элементы в массиве что элемент со значением k окажется в nums[k - 1] если 0 <= k - 1 < nums.length. Элементы со значениями вне этого диапазона случайно распределяются на оставшиеся свободными места.

Будем идти по массиву и если встретим элемент который можно поставить на место и на его месте чужой элемент, поменяем их местами. Обмены повторяем пока элементы становятся на свои места, затем переходим к следующему индексу. Когда пройдём весь массив, окажется что все элементы, которые можно было поставить на место, уже на своих местах. Ещё один цикл ищет места без своего элемента, этот элемент и пропущен.

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

class Solution {
    public int firstMissingPositive(int[] nums) {
        for (int i = 0; i < nums.length; ++i) {
            for (; ; ) {
                int j = nums[i];
                if (1 <= j && j <= nums.length) {
                    int k = j - 1;
                    if (nums[k] != nums[i]) {
                        int temp = nums[k];
                        nums[k] = nums[i];
                        nums[i] = temp;
                        continue;
                    }
                }
                break;
            }
        }
        for (int i = 0; i < nums.length; ++i) {
            if (nums[i] != i + 1) {
                return i + 1;
            }
        }
        return nums.length + 1;
    }
}

БЛОГ НА HUSL

Ускорить код Java

Ответы (1 шт):