TopK问题——找出100万个数中的前K个最大的
程序员文章站
2024-03-15 22:05:00
...
大体思路是:
- 首先将100万条数据分割,这里演示的分割为100份
- 将这一百份中的数据进行快速排序
- 将一百分排序好的数据找出最大的组成一个长度为100的新数组
- 对新数组进行快速排序
- 找出前K个最大的数病输出
废话不多说,下面是代码,也可以通过码云进行下载点击查看
import java.util.List;
import java.util.ArrayList;
import java.util.Scanner;
/**
* TopK问题
* @author 胡海龙<[email protected]>
*/
public class QuicklySort{
public static void main(String[] args) {
//指定数组,这里可以替换为题目中的100万数据
int[] arr = {19,18,17,6,5,4,3,2,1,7,8,11,9,10,13,12};
//将100万数据分割为100份,每份为1万,这里是我的测试数据长度为12,每份分6
int[][]arrays = splitArr(arr, 8);
//声明一个大小为分割份数的数组
int[]finallyArray = new int[arrays.length];
//对一百份数组进行快速排序
for(int i=0; i<arrays.length; i++){
sort(arrays[i],0,arrays[i].length-1);
printArr(arrays[i]);
int temp = arrays[i][arrays[i].length-1];
finallyArray[i] = temp;
}
//最终我们将自己声明的数组进行快速排序即可
sort(finallyArray, 0, finallyArray.length-1);
//这时候我们需要找前K个最大的对应的进行找即可
Scanner sc = new Scanner(System.in);
System.out.print("plase input k value:");
int k = sc.nextInt();
sc.close();
//输出前K位
for(int i=0; i<k; i++){
System.out.print(finallyArray[i]+" ");
}
}
//快速排序
public static void sort(int[]array,int low, int hight){
if(low>hight){
return;
}
int left = low;
int right = hight;
int pivot = array[low];
while(left<right){
while(array[right]>pivot && left<right){
right--;
}
while(array[left]<=pivot && left<right){
left++;
}
if(left<right){
int temp = array[left];
array[left] = array[right];
array[right] = temp;
}
}
array[low] = array[right];
array[right] = pivot;
sort(array, low, right-1);
sort(array, right+1, hight);
}
//分割数组
public static int[][] splitArr(int[]array,int subSize){
List<List<Integer>> list = new ArrayList<>();
int count = array.length%subSize == 0 ? array.length/subSize : array.length/subSize + 1;
for(int i=0; i<count; i++){
int index = i*subSize;
List<Integer> temp = new ArrayList<>();
int j = 0;
while(j<subSize && index<array.length){
temp.add(array[index++]);
j++;
}
list.add(temp);
}
int[][]newarray = new int[list.size()][];
for(int i=0; i<list.size(); i++){
List<Integer> subList = list.get(i);
int[]subArrItem = new int[subList.size()];
for(int j=0; j<subList.size(); j++){
subArrItem[j] = subList.get(j).intValue();
}
newarray[i] = subArrItem;
}
return newarray;
}
//打印数组
public static void printArr(int[]array){
for(int x : array){
System.out.print(x+" ");
}
System.out.println();
}
}
上一篇: Top K 问题
下一篇: java求一个数组的最大值和最小值