题目描述
输入n个整数,找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字,则最小的4个数字是1,2,3,4,。
思路分析
两种思路可以实现,第一种是利用插入排序来实现,首先维持一个长度为K
的有序序列,然后将剩下的数字插入到有序序列中去,直到最后一个元素,插入排序结束后就前面K
个元素就是最小的K
个数;
第二种是利用快速排序来实现,需要改动一下,判断每次返回的partition
位置是否等于K
,根据返回的位置下标进行左右递归分治,直到最终返回的partition
位置等于K
时,前面K
个元素就是题目要求的最小K
个数;
代码实现
import java.util.ArrayList;
public class Solution {
/**
* 链接:https://www.nowcoder.com/questionTerminal/6a296eb82cf844ca8539b57c23e6e9bf?answerType=1&f=discussion
* 来源:牛客网
* 维持一个K长度的最小值集合,然后利用插入排序的思想进行对前K个元素的不断更新。
*/
public ArrayList<Integer> GetLeastNumbers_Solution(int[] input, int k) {
ArrayList<Integer> result = new ArrayList<Integer>();
if (k <= 0 || k > input.length)
return result;
//初次排序,完成k个元素的排序
for (int i = 1; i < k; i++) {
int j = i - 1;
int unFindElement = input[i];
while (j >= 0 && input[j] > unFindElement) {
input[j + 1] = input[j];
j--;
}
input[j + 1] = unFindElement;
}
//遍历后面的元素 进行k个元素的更新和替换
for (int i = k; i < input.length; i++) {
if (input[i] < input[k - 1]) {
int newK = input[i];
int j = k - 1;
while (j >= 0 && input[j] > newK) {
input[j + 1] = input[j];
j--;
}
input[j + 1] = newK;
}
}
//把前k个元素返回
for (int i = 0; i < k; i++)
result.add(input[i]);
return result;
}
/**
* 链接:https://www.nowcoder.com/questionTerminal/6a296eb82cf844ca8539b57c23e6e9bf?answerType=1&f=discussion
* 来源:牛客网
* <p>
* 快排的partition函数会将原序列分为左右两个子序列,左边序列都小于pivot,右边序列都大于或等于pivot,
* 当pivot为数组的第k个元素时,数组中pivot及其之前的元素都小于右边序列,即为n个整数中最小的k个数。
*/
public ArrayList<Integer> GetLeastNumbers_SolutionV2(int[] input, int k) {
if (input == null || input.length == 0 || input.length < k || k == 0) {
return new ArrayList<>();
}
// 在数组中寻找位置为k - 1的pivot
int start = 0, end = input.length - 1;
int index = partition(input, start, end);
while (index != k - 1) {
if (index < k - 1) {
start = index + 1;
} else {
end = index - 1;
}
index = partition(input, start, end);
}
// 收集这k个数
ArrayList<Integer> res = new ArrayList<>();
for (int i = 0; i <= index; i++) {
res.add(input[i]);
}
return res;
}
// divide target range array to smaller hi value part and other part.
private int partition(int[] arr, int start, int end) {
int pivot = arr[end];
int prePtr = start - 1;
while (start < end) {
if (arr[start] < pivot) {
swap(arr, start++, ++prePtr);
} else {
start++;
}
}
swap(arr, end, ++prePtr);
return prePtr;
}
private void swap(int[] arr, int a, int b) {
int temp = arr[b];
arr[b] = arr[a];
arr[a] = temp;
}
public static void main(String[] args) {
int[] array = {4, 5, 1, 6, 2, 7, 3, 8};
Q40_MinimumNumberOfK q40MinimumNumberOfK = new Q40_MinimumNumberOfK();
// ArrayList<Integer> arrayList = solution23.GetLeastNumbers_Solution(array, 4);
ArrayList<Integer> arrayList = q40MinimumNumberOfK.GetLeastNumbers_SolutionV2(array, 4);
System.out.println(arrayList);
System.out.println(Arrays.toString(array));
}
}
网友评论