Сначала отсутствует временная сложность целочисленного подхода

Question

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

public int firstMissingPositive(int[] A) {
        int l = A.length;
        int i = 0;
        while (i < l) {
            int j = A[i];
            while (j > 0 && j <= l) {
                int k = A[j - 1];
                A[j - 1] = Integer.MAX_VALUE;
                j = k;
            }
            i++;
        }
        for (i = 0; i < l; i++) {
            if (A[i] != Integer.MAX_VALUE)
                break;
        }
        return i + 1;
    }

Наблюдения и выводы: Глядя на структуру l oop I Я подумал, что сложность должна быть больше чем n, так как я могу посещать каждый элемент более двух раз в некоторых случаях. Но, к моему удивлению, решение было принято. Я не могу понять сложность.

Answer 1

Вы, вероятно, смотрите на вложенные циклы и думаете O (N ² ), но это не так просто.

Каждая итерация внутреннего l oop меняет элемент в A до Integer.MAX_VALUE, и есть только N элементов, поэтому не может быть более N внутренних итераций l oop в общей сложности .

Таким образом, общее время O (N).