この質問を受け取ったら、まず並べ替えを考えます。並べ替えた後、最大の K 番号を選択します。並べ替えの選択 クイック並べ替えを選択することをお勧めします。
さて、最初の解決策であるクイックソートを実行しましょう
コードは次のとおりです
次のようにコードをコピーします。
public static void QuickSort(int[] arr, int start, int end) {
if (開始 < 終了) {
int キー = arr[開始];
int right = 開始;
int left = 終了;
while (右 < 左) {
while (右 < 左 && arr[左] > キー) {
左 - ;
}
if (右 < 左) {
arr[右] = arr[左];
}
while (right < left && arr[right] <= key) {
右++;
}
if (右 < 左) {
arr[左] = arr[右];
}
}
arr[右] = キー;
QuickSort(arr, start, right-1);
クイックソート(arr, left+1, end);
}
}
簡単に並べ替えると、配列は小さい順に並べられるため、出力は次のようになります。
次のようにコードをコピーします。 int k = 4;
for (int i=arr.length-1; i>=arr.length-k; i--) {
System.out.println(arr[i]+" ");
}
。最初の解決策はすでに優れていますが、より良い方法はあるでしょうか?
答えは「はい」です！部分的な並べ替えを選択し、選択並べ替えを使用してこの問題を解決します。
コードは次のとおりです。
次のようにコードをコピーします。 public static int[] selectSortK(int[] arr, int k) {
if(arr == null || arr.length == 0) {
null を返します。
}
int[] newArr = 新しい int[k];
List<Integer> list = new ArrayList<Integer>();//毎回最大数の添え字を記録する
for (int i=0; i<k; i++) {
int maxValue = Integer.MIN_VALUE; //最大値
int maxIndex = i;
for (int j=0; j<arr.length; j++) {
if (arr[j] > maxValue && !list.contains(j) ) {
maxValue = arr[j];
maxIndex = j;
}
}
if (!list.contains(maxIndex)) {//存在しない場合は追加します
list.add(maxIndex);
newArr[i] = maxValue;
}
}
newArr を返します。
}