ここまで O(n) のアルゴリズムのものが出ていないようですので、投稿します。
解説記事は気が向いたらそのうち書きます。⇒書きました。
public static int[] makeRandomArray1(Random rand, int size, int randMin, int randMax) {
// パラメータチェック
// （略）
// 本処理
int[] randArray = new int[size];
Map<Integer, Integer> conversion = new HashMap<>();
for (int i = 0, upper = randMax - randMin + 1; i < size; i++, upper--) {
int key = rand.nextInt(upper);
int val = conversion.getOrDefault(key, key);
randArray[i] = val + randMin;
conversion.put(key, conversion.getOrDefault(upper - 1, upper - 1));
conversion.remove(upper - 1); // この行はメモリ節約のためのもの。無くても動く。
}
return randArray;
}
ポイントは「本処理」の部分が計算量 O(size) のアルゴリズムであることです。
size が大きくなっても衝突による性能劣化は生じません。
また、randMin～randMax の範囲が大きくなっても性能劣化は生じません。（randMin～randMax の広さによる影響を受けません。）
最近のパソコンは性能が良いので力づくでやっちゃえば良いじゃん、という意見もあるかもしれません。性能のことを考えずコーディングの手間だけを考えるのであれば、今や次のコードが一番簡単ですね。1
public static int[] makeRandomArray2(Random rand, int size, int randMin, int randMax) {
// makeRandomArray1 と同じパラメータチェックを実施（記載略）
return rand.ints(randMin, randMax + 1).distinct().limit(size).toArray();
}
-
みなさん、たとえば後輩がこのコードを持ってきたらレビューで弾きますか？ 測定はしていませんが、きっと1万件くらいまでなら実用時間で通るんだろうなぁ、と。ソースコードの見た目がとてもスマートなだけに悩ましいところだなあと感じました。私なら、アルゴリズム上の問題を理解しているか本人に確認し、理解したうえで敢えて採用しているのであれば通しちゃうかなぁ... ↩