[プログラマー/sort/level 1]k個数
問題の主なタイプ
quicksort
解決策
pivotを基準に値を分割します.
分割の結果をもとに、それを左右に分ける
분할 정복
問題で与えられた対応するインデックスの値をlistに格納します.
保存したリストをarrayに変換します.
ノートをまちがえる
QuickSortはほとんど暗記されていますが、ライブラリで提供されているソート方法をよく使うので、直接実現するのは難しいです.
再帰関数をもっと練習して、慣れます.
学識
QuickSortの時間的複雑さ
O(NlogN)
最悪O(N^2)
基本Collection Frameworkで昇順に並べたい場合は、
List<Integer> list = new ArrayList<>();
list.sort(Comparator.naturalOrder());
解題コード
import java.util.ArrayList;
import java.util.List;
class Solution {
public int[] solution(int[] arr, int[][] commands) {
List<Integer> answerList = new ArrayList<>();
for (int[] command : commands) {
int start = command[0] - 1;
int end = command[1] - 1;
int[] tempArr = new int[end - start + 1];
int findIndex = command[2] - 1;
int index = 0;
for (int i = start; i <= end; i++) {
tempArr[index++] = arr[i];
}
quickSort(tempArr, 0, tempArr.length - 1);
answerList.add(tempArr[findIndex]);
}
return answerList.stream().mapToInt(i -> i).toArray();
}
private void quickSort(int[] arr, int start, int end) {
int left = start;
int right = end;
int mid = (start + end) / 2;
int pivot= arr[mid];
do {
while(arr[left] < pivot) {
left++;
}
while(arr[right] > pivot) {
right--;
}
if(left <= right) {
swap(arr, left, right);
left++;
right--;
}
}while(left <= right);
if(start < right) {
quickSort(arr, start, right);
}
if(end > left) {
quickSort(arr, left, end);
}
}
private void swap(int[] arr, int left, int right) {
int temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
}
}
Reference
この問題について([プログラマー/sort/level 1]k個数), 我々は、より多くの情報をここで見つけました https://velog.io/@pbg0205/프로그래머스정렬level1-k번째-수テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol