JavaでK番目に大きい要素を見つける方法

投稿日: 2019-10-18 2022-10-25
タグ: Algorithms, Java

1. 序章

この記事では、一意の番号のシーケンスでk番目に大きい要素を見つけるためのさまざまなソリューションを紹介します。例では整数の配列を使用します。

また、各アルゴリズムの平均および最悪の場合の時間計算量についても説明します。

2. ソリューション

次に、いくつかの可能な解決策を見てみましょう。1つはプレーンソートを使用し、2つはクイックソートから派生したクイックセレクトアルゴリズムを使用します。

2.1. 並べ替え

問題について考えるとき、おそらく頭に浮かぶ最も明白な解決策は、配列をソートするです。

必要な手順を定義しましょう。

配列を昇順で並べ替えます
配列の最後の要素が最大の要素になるため、k番目に大きい要素はxthインデックスになります。ここで、 x = length（array）– k [X159X ]

ご覧のとおり、解決策は簡単ですが、配列全体を並べ替える必要があります。したがって、時間計算量は O（n * logn）になります。

public int findKthLargestBySorting(Integer[] arr, int k) {
    Arrays.sort(arr);
    int targetIndex = arr.length - k;
    return arr[targetIndex];
}

別の方法は、配列を降順で並べ替えて、（k-1）番目のインデックスの要素を返すことです。

public int findKthLargestBySortingDesc(Integer[] arr, int k) {
    Arrays.sort(arr, Collections.reverseOrder());
    return arr[k-1];
}

2.2. クイックセレクト

これは、以前のアプローチの最適化と見なすことができます。ここでは、QuickSortを選択して並べ替えます。問題の説明を分析すると、実際には配列全体を並べ替える必要はなく、配列のk番目の要素がk番目に大きいまたは最小になるように内容を並べ替えるだけでよいことがわかります。

クイックソートでは、ピボット要素を選択して正しい位置に移動します。また、その周りの配列を分割します。 QuickSelectでは、ピボット自体がk番目に大きい要素であるポイントで停止するという考え方です。

ピボットの左側と右側の両方で繰り返さない場合は、アルゴリズムをさらに最適化できます。ピボットの位置に応じて、そのうちの1つだけを繰り返す必要があります。

QuickSelectアルゴリズムの基本的な考え方を見てみましょう。

ピボット要素を選択し、それに応じて配列を分割します
- 右端の要素をピボットとして選択します
- ピボット要素が正しい場所に配置されるように配列を再シャッフルします。ピボットよりも小さい要素はすべて低いインデックスに配置され、ピボットよりも大きい要素はピボットよりも高いインデックスに配置されます。
ピボットが配列のk番目の要素に配置されている場合、ピボットは k 番目に大きい要素であるため、プロセスを終了します。
ピボット位置がk、より大きい場合は、左側のサブアレイでプロセスを続行します。それ以外の場合は、右側のサブアレイでプロセスを繰り返します。

k番目に小さい要素を見つけるために使用できる汎用ロジックを作成することもできます。ソートされた配列のk番目の要素を返すメソッドfindKthElementByQuickSelect（）を定義します。

配列を昇順で並べ替えると、配列のk番目の要素がk番目に小さい要素になります。を見つけるには k 最大の要素、渡すことができます k = length（Array）–k。

このソリューションを実装しましょう：

public int 
  findKthElementByQuickSelect(Integer[] arr, int left, int right, int k) {
    if (k >= 0 && k <= right - left + 1) {
        int pos = partition(arr, left, right);
        if (pos - left == k) {
            return arr[pos];
        }
        if (pos - left > k) {
            return findKthElementByQuickSelect(arr, left, pos - 1, k);
        }
        return findKthElementByQuickSelect(arr, pos + 1,
          right, k - pos + left - 1);
    }
    return 0;
}

次に、パーティションメソッドを実装します。このメソッドは、右端の要素をピボットとして選択し、適切なインデックスに配置し、低いインデックスの要素がピボット要素よりも小さくなるように配列をパーティション化します。

同様に、より高いインデックスの要素は、ピボット要素よりも大きくなります。

public int partition(Integer[] arr, int left, int right) {
    int pivot = arr[right];
    Integer[] leftArr;
    Integer[] rightArr;

    leftArr = IntStream.range(left, right)
      .filter(i -> arr[i] < pivot)
      .map(i -> arr[i])
      .boxed()
      .toArray(Integer[]::new);

    rightArr = IntStream.range(left, right)
      .filter(i -> arr[i] > pivot)
      .map(i -> arr[i])
      .boxed()
      .toArray(Integer[]::new);

    int leftArraySize = leftArr.length;
    System.arraycopy(leftArr, 0, arr, left, leftArraySize);
    arr[leftArraySize+left] = pivot;
    System.arraycopy(rightArr, 0, arr, left + leftArraySize + 1,
      rightArr.length);

    return left + leftArraySize;
}

パーティショニングを実現するための、より単純で反復的なアプローチがあります。

public int partitionIterative(Integer[] arr, int left, int right) {
    int pivot = arr[right], i = left;
    for (int j = left; j <= right - 1; j++) {
        if (arr[j] <= pivot) {
            swap(arr, i, j);
            i++;
        }
    }
    swap(arr, i, right);
    return i;
}

public void swap(Integer[] arr, int n1, int n2) {
    int temp = arr[n2];
    arr[n2] = arr[n1];
    arr[n1] = temp;
}

このソリューションは、平均して O（n）時間で機能します。ただし、最悪の場合、時間計算量は O（n ^ 2）になります。

2.3. ランダム化されたパーティションを使用したQuickSelect

このアプローチは、以前のアプローチを少し変更したものです。配列がほぼ/完全にソートされていて、右端の要素をピボットとして選択した場合、左右のサブ配列のパーティションは非常に不均一になります。

この方法は、最初のピボット要素をランダムに選択することを提案します。ただし、パーティショニングロジックを変更する必要はありません。

partition を呼び出す代わりに、 randomPartition メソッドを呼び出します。これは、ランダムな要素を選択し、それを右端の要素と交換してから、最終的にpartitionメソッドを呼び出します。

randomPartitionメソッドを実装しましょう。

public int randomPartition(Integer arr[], int left, int right) {
    int n = right - left + 1;
    int pivot = (int) (Math.random()) * n;
    swap(arr, left + pivot, right);
    return partition(arr, left, right);
}

このソリューションは、ほとんどの場合、前のケースよりもうまく機能します。

ランダム化されたクイックセレクトの予想される時間計算量はO（n）です。

ただし、最悪の時間計算量は依然として O（n ^ 2）です。

3. 結論

この記事では、一意の数値の配列から k 番目に大きい（または最小の）要素を見つけるためのさまざまなソリューションについて説明しました。最も簡単な解決策は、配列を並べ替えてk番目の要素を返すことです。このソリューションの時間計算量はO（n * logn）です。

また、クイックセレクトの2つのバリエーションについても説明しました。このアルゴリズムは単純ではありませんが、平均的な場合、 O（n）の時間計算量があります。

いつものように、アルゴリズムの完全なコードはGitHubのにあります。

getdocs

13036