[JAVA] [100%] MissingInteger (src & junit & author's note)

Respectable

MissingInteger

Find the smallest positive integer that does not occur in a given sequence.

Task description

Write a function:

class solution {public int solution（int [] A）; }

Given an array A of N integers, it returns the smallest positive integer (greater than 0) that does not occur in A.

For example, if A = [1, 3, 6, 4, 1, 2], then the function should return 5.

If A = [1, 2, 3], the function must return 4.
If A = [-1, -3], the function must return 1.

Write an efficient algorithm for the following assumptions:

N is an integer in the range [1..100,000].
Each element of array A is an integer in the range [-1,000,000..1,000,000].

Author's note

There are many solutions to this problem. In this article, I would like to introduce you to the basic data structure "bucket", which is also one of the most commonly used data structures in large user scenarios. For example, in a scenario with hundreds of millions of active users, if you want to use a cache cluster to achieve a user's "N days of continuous login ..." functionality, you can adopt this data structure and use the cache invalidation time. At the same time, high-performance business functions can be easily realized.

Roc Yang: The solution to the problem, the main text, the basic number structure "Bucket", and the regular number structure in the scene for the amount of sea. Under the scene of the cache activity, the cache cache, the cache cache, the cache cache, the cache cache, the cache cache, the cache cache, the cache cache, the cache cache, the cache cache, the cache cache, the cache cache, the cache cache, the cache cache, the cache cache, and the cache cache ..

solve

Program MissingIntegerSolution.java

`MissingIntegerSolution.java`


    public int solution(int[] A) {
        boolean[] B = new boolean[1000001];
        java.util.Arrays.fill(B, false);
        for (int i = 0; i < A.length; i++) {
            if (A[i] > 0) {
                B[A[i]] = true;
            }
        }
        for (int j = 1; j < B.length; j++) {
            if (!B[j]) return j;
        }

        return 1000001;
    }

Detected time complexity:
O(N) or O(N * log(N))

jUnit MissingIntegerSolutionTest.java

Report Candidate Report: training33X6JS-SN7