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

Respectable

MissingInteger

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

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.

Write an efficient algorithm for the following assumptions:


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

image.png

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


Recommended Posts

[100%] MissingInteger (src & junit & author's note)
[100%] [GenomicRangeQuery] (src & junit & author's note)
[100%] MaxCounters (src & junit & author's note)
[100%] Distinct (src & junit & author's note)
[100%] CountDiv (src & junit & author's note)
[100%] CyclicRotation (src & jUnit)
[100%] FrogJmp (src & jUnit)
[100%] FrogRiverOne (src & jUnit)
[100%] OddOccurrencesInArray (src & jUnit)
[100%] MinAvgTwoSlice (src & junit)
[100%] PassingCars (src & junit)
[100%] PermCheck (src & junit)
[100%] TapeEquilibrium (src & jUnit)
[100%] MaxProductOfThree (src & jUnit)
[100%] BinaryGap (src & jUnit)
Java JUnit brief note