配列から重複要素を効率的に削除することは、プログラミングにおける基本的なタスクです。この記事では、速度とメモリ使用量のバランスがそれぞれ異なる3つの異なるJavaアプローチについて説明します。これらのトレードオフを理解することは、特定のアプリケーションに最適な方法を選択するために不可欠です。
目次
一時配列を使用する
この簡単な方法は、入力配列を反復処理します。各要素は、これまでに遭遇した一意の要素のみを含む一時配列に対してチェックされます。要素が一時配列に見つからない場合は、追加されます。理解しやすい一方で、ネストされたループ構造により、時間計算量がO(n²)となり、大規模な配列では非効率になります。
import java.util.Arrays;
public class RemoveDuplicates {
public static int[] removeDuplicatesTempArray(int[] arr) {
if (arr == null || arr.length == 0) {
return new int[0];
}
int[] uniqueArr = new int[arr.length];
int uniqueCount = 0;
for (int i = 0; i < arr.length; i++) {
boolean isDuplicate = false;
for (int j = 0; j < uniqueCount; j++) {
if (arr[i] == uniqueArr[j]) {
isDuplicate = true;
break;
}
}
if (!isDuplicate) {
uniqueArr[uniqueCount++] = arr[i];
}
}
return Arrays.copyOf(uniqueArr, uniqueCount);
}
public static void main(String[] args) {
int[] arr = {1, 2, 2, 3, 4, 4, 5, 5, 5};
int[] uniqueArr = removeDuplicatesTempArray(arr);
System.out.println("元の配列: " + Arrays.toString(arr));
System.out.println("重複を削除した配列: " + Arrays.toString(uniqueArr));
}
}
時間計算量: O(n²)
空間計算量: O(n)
個別インデックスを使用する
この方法は、元の配列をインプレースで変更することで、空間効率を向上させます。次のユニークな要素の位置を追跡するために、個別のインデックスを使用します。配列は反復処理され、一意の要素はこのインデックスで示された位置に移動されます。空間効率が高い（O(1)）一方で、ネストされたループのため、時間計算量は依然としてO(n²)です。
public class RemoveDuplicates {
public static int[] removeDuplicatesIndex(int[] arr) {
if (arr == null || arr.length == 0) {
return new int[0];
}
int index = 1;
for (int i = 1; i < arr.length; i++) {
boolean isDuplicate = false;
for (int j = 0; j < index; j++) {
if (arr[i] == arr[j]) {
isDuplicate = true;
break;
}
}
if (!isDuplicate) {
arr[index++] = arr[i];
}
}
return Arrays.copyOf(arr, index);
}
//mainメソッドは上記と同じ
}
時間計算量: O(n²)
空間計算量: O(1)
Arrays.sort()メソッドを使用する
このアプローチは、Javaの組み込みソート機能を利用します。配列を最初にソートすると、重複する要素が一緒に配置されます。ソートされた配列を一度通過することで、各要素の最初の出現のみを識別して保持します。時間計算量はソートアルゴリズム（O(n log n)）が支配的であり、以前の方法よりも大規模なデータセットで大幅にパフォーマンスが向上します。
import java.util.Arrays;
public class RemoveDuplicates {
public static int[] removeDuplicatesSort(int[] arr) {
if (arr == null || arr.length == 0) {
return new int[0];
}
Arrays.sort(arr);
int[] uniqueArr = new int[arr.length];
uniqueArr[0] = arr[0];
int uniqueCount = 1;
for (int i = 1; i < arr.length; i++) {
if (arr[i] != arr[i - 1]) {
uniqueArr[uniqueCount++] = arr[i];
}
}
return Arrays.copyOf(uniqueArr, uniqueCount);
}
//mainメソッドは上記と同じ
}
時間計算量: O(n log n)
空間計算量: O(n)
メソッド比較
メソッドの選択は、データのサイズと優先順位によって異なります。小規模な配列の場合、一時配列メソッドの簡潔さで十分な場合があります。大規模な配列の場合、Arrays.sort()メソッドのパフォーマンス向上は、わずかに高い空間計算量を上回ります。個別インデックスメソッドは空間効率の高いソリューションを提供しますが、2乗の時間計算量のため、大規模なデータセットでは魅力が低くなります。