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
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