Respectable

MissingInteger

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

タスク説明

関数を書く：

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

これは、N個の整数の配列Aが与えられた場合、Aで発生しない最小の正の整数（0より大きい）を返します。

たとえば、A = [1、3、6、4、1、2]の場合、関数は5を返す必要があります。

A = [1、2、3]の場合、関数は4を返す必要があります。
A = [-1、-3]の場合、関数は1を返す必要があります。

次の仮定のための効率的なアルゴリズムを記述します。

Nは[1..100,000]の範囲内の整数です。
配列Aの各要素は、[-1,000,000..1,000,000]の範囲内の整数です。

著者注

当該問題には多くの解決策があります。
この記事では、大規模なユーザーシナリオでよく使用されるデータ構造の1つでもある、基本的なデータ構造「バケット」を紹介したいと思います。
たとえば、数億人のアクティブユーザーのシナリオで、キャッシュクラスターを使用してユーザーの「N日間の連続ログイン...」機能を実現する場合、このデータ構造を採用でき、キャッシュの無効化時間の使用を併せて、高性能の業務機能を簡単的に実現できます。

Roc Yang:
本题解法有很多，本文想介绍一种基本数据结构“Bucket”，也是海量用户场景下常用的数据结构之一。比如亿级活跃用户场景下，使用缓存集群实现用户“连续登陆N天...”功能时，就可以采用这种数据结构，配合缓存的失效时间，很方便的实现高性能的此类业务功能。

解く

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

See also: CodilityのLessonsをすべて解く（更新中）