Find the largest K number solution in JAVA
- 2020-04-01 03:16:49
- OfStack
So the first thing you want to do when you get this problem is sort it, sort it out and then pick and choose the largest number of K. Sort selection quicksort is a good choice.
Well, let's do the first solution: quicksort
The following code
public static void quickSort(int[] arr, int start, int end) {
if (start < end) {
int key = arr[start];
int right = start;
int left = end;
while (right < left) {
while (right < left && arr[left] > key) {
left --;
}
if (right < left) {
arr[right] = arr[left];
}
while (right < left && arr[right] <= key) {
right ++;
}
if (right < left) {
arr[left] = arr[right];
}
}
arr[right] = key;
quickSort(arr, start, right-1);
quickSort(arr, left+1, end);
}
}
After quicksort, the array is going to be ordered, and the sorting at the top is going to be from small to large, so our output should look like this
int k = 4;
for (int i=arr.length-1; i>=arr.length-k; i--) {
System.out.println(arr[i]+" ");
}
. The first solution is good, but there is no better way.
The answer is yes! We can select partial sort, and then we can use selection sort to solve this problem.
The code is as follows:
public static int[] selectSortK(int[] arr, int k) {
if(arr == null || arr.length == 0) {
return null;
}
int[] newArr = new int[k];
List<Integer> list = new ArrayList<Integer>();//Record the index of the largest number at each time
for (int i=0; i<k; i++) {
int maxValue = Integer.MIN_VALUE; //The maximum
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)) {//If it doesn't exist, join it
list.add(maxIndex);
newArr[i] = maxValue;
}
}
return newArr;
}