使用O(1)辅助空间以相同顺序在阵列中找到k个最小数的算法

Question

例如,如果数组是 arr [] = {4,2,6,1,5}和k = 3,则输出应为4 2 1.

Answer 1

首先找到数组中第 K 个最小的数。

看看https://www.geeksforgeeks.org/kth-smallestlargest-element-unsorted-array-set-2-expected-linear-time/

上面的链接显示了如何使用随机快速选择来在average complexityO(n) 时间内找到第 k 个最小元素。

一旦获得第 K 个最小元素，循环遍历数组并打印所有等于或小于第 K 个最小数字的元素。

    int small={Kth smallest number in the array}
    for(int i=0;i<array.length;i++){
         if(array[i]<=small){
            System.out.println(array[i]+ " ");  
       }

}