이 질문을 받은 후에는 먼저 정렬을 생각한 후 가장 큰 K 숫자를 선택합니다. 정렬 선택 빠른 정렬이 더 나은 선택입니다.
자, 첫 번째 해결 방법인 퀵 정렬을 해보겠습니다.
코드는 다음과 같습니다
다음과 같이 코드 코드를 복사합니다.
공개 정적 무효 QuickSort(int[] arr, int start, int end) {
if (시작 < 끝) {
int 키 = arr[시작];
int 오른쪽 = 시작;
int 왼쪽 = 끝;
동안 (오른쪽 < 왼쪽) {
while (오른쪽 < 왼쪽 && arr[왼쪽] > 키) {
왼쪽 --;
}
if (오른쪽 < 왼쪽) {
arr[오른쪽] = arr[왼쪽];
}
while (오른쪽 < 왼쪽 && arr[오른쪽] <= 키) {
그렇죠++;
}
if (오른쪽 < 왼쪽) {
arr[왼쪽] = arr[오른쪽];
}
}
arr[오른쪽] = 키;
QuickSort(arr, start, right-1);
QuickSort(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];
최대 인덱스 = j;
}
}
if (!list.contains(maxIndex)) {//존재하지 않으면 추가하세요.
list.add(maxIndex);
newArr[i] = 최대값;
}
}
newArr을 반환합니다.
}