0

配列内の th 要素を取得するためにクイック選択アルゴリズムを実装していkますが、解決方法がわからない場所で立ち往生しています。動作しない私のコードは次のとおりです。

public static void main (String[] args) {
    int[] arr = new int[]{7,6,5,4,3,2,1}; 
    int k = 4;
    quickSort(arr, 0, arr.length - 1, k);
    return arr[k];
}

private static void quickSelect(int[] nums, int start, int end, int k) {
    if (start < end) {
        int partitionIndex = getPartitionIndex(nums, start, end);
        if (partitionIndex == k) {
            return;
        }
        quickSelect(nums, start, partitionIndex - 1, k);
        quickSelect(nums, partitionIndex + 1, end, k);
    }
}

private int getPartitionIndex(int[] nums, int start, int end) {
    int pivot = nums[end];
    int index = start;
    for (int i = start; i <= end; i++) {
        int current = nums[i];
        if (current < pivot) {
            swap(nums, index, i);
            index++;
        }
    }
    swap(nums, index, end);
    return index;
}

private void swap(int[] nums, int i, int j) {
    if (i == j) {
        return;
    }
    nums[i] = nums[i] ^ nums[j];
    nums[j] = nums[i] ^ nums[j];
    nums[i] = nums[i] ^ nums[j];
}

確かに、これらの行を削除すると:

        if (partitionIndex == k) {
            return;
        }

クイックソートになり、正常に動作します。そして、それが機能しない理由を理解しています。これは、上記の条件で戻ったときに、0 から k まで取得している配列がソートされていない可能性があるためです。しかし、配列内の最初の k 個の要素のみを並べ替えて残りを除外する適切な条件を見つけることができないため、余分な作業を行う必要はありません。私はオンラインでいくつかの実装を見て、上記に時間を費やしましたが、それを理解することができなかったので、助けを求めてください.

4

1 に答える 1

1

k < partitionIndex の場合は左側のパーティションのみをチェックし、それ以外の場合は右側のパーティションのみをチェックします。

        if (k < partitionIndex)
            quickSelect(nums, start, partitionIndex - 1, k);
        else
            quickSelect(nums, partitionIndex + 1, end, k);
于 2021-06-13T06:59:34.480 に答える