输入包含两行，第一行包含两个整数n和k(1≤k≤n≤105)，代表数组arr的长度，第二行包含n个整数，代表数组arr。
 
输出描述:
 
输出包含一行，k个整数，代表数组中最小的k个整数。
 
备注:
 
时间复杂度O(nlog_2k)和O(n)O(nlog2​k)和O(n)，额外空间复杂度O(n)O(n)
 
​​​​​​​public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    System.out.println("请输入数组长度n和输出最小k个整数，以空格隔开");
    String[] num = sc.nextLine().split(" ");
    while (num.length <2 || Integer.parseInt(num[0]) < Integer.parseInt(num[1])){
        System.out.println("输入格式有误，请重新输入");
        num = sc.nextLine().split(" ");
    }
    int n = Integer.parseInt(num[0]);
    int k = Integer.parseInt(num[1]);
    System.out.println("请输入数组arr，数字之间以空格隔开");
    String[] inputArr = sc.nextLine().split(" ");
    int[] numArr = new int[inputArr.length];
    for (int i = 0;i< inputArr.length;i++){
        numArr[i] = Integer.parseInt(inputArr[i]);
    }
    // 需要输出最小k个数的数组
    int[] outputArr = new int[k];
    // 默认取原数组前k个填充输出数组
    if (k >= 0) System.arraycopy(numArr, 0, outputArr, 0, k);
    // 排序
    Arrays.sort(outputArr);
    for (int i=k;i< numArr.length;i++) {
           // 如果第i个数比输出数组的最后一位小，说明需要放入输出数组
        if (numArr[i] < outputArr[k - 1]) {
            // 数组后移
            change(outputArr,numArr[i]);
        }
    }
    for (int i = 0; i < k; i++) {
        System.out.print(outputArr[i] + " ");
    }
}

public static void change(int []a,int x){
    int i=0;
    for (;i<a.length;i++){
          // 找到需要后移的索引
        if(x<a[i])break;
    }
// 通过数组复制实现数组后移
    if (a.length - 1 - i >= 0) System.arraycopy(a, i, a, i + 1, a.length - 1 - i);
    a[i]=x;
}
 
 

题目描述
 给定一个数组，找出其中最小的K个数。例如数组元素是4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4。如果K>数组的长度，那么返回一个空的数组
 
class Solution:
    def GetLeastNumbers_Solution(self, tinput, k):
        # write code here
        if k>len(tinput):
            return []
        tinput.sort()
        return tinput[:k]

if __name__ == '__main__':
    tinput=[2,3,8,1,5,6,9,6,8]
    k=3
    a = Solution()
    num=a.GetLeastNumbers_Solution(tinput,k)
    print(num)

力扣面试题 17.14. 最小K个数
 设计一个算法，找出数组中最小的k个数。以任意顺序返回这k个数均可。
 示例：
 输入： arr = [1,3,5,7,2,4,6,8], k = 4
 输出： [1,2,3,4]
 提示：数组内的数输出顺序可以不同。
 0 <= len(arr) <= 100000
 0 <= k <= min(100000, len(arr))
 
使用堆排序
 使用原数组的前k个元素创建一个最大堆，剩余元素与最大堆的首元素比较，若较之更小，则与之替换，遍历后就可以得到原数组中的最小k个数。
 
代码如下：
 
class Solution {
public:
   vector<int> smallestK(vector<int>& arr, int k) {
        vector<int> vec;
        if (k == 0)
            return vec;
        vec.resize(k);
        int maxindex = k - 1, curindex = (maxindex - 1) / 2,n = arr.size();
        for (int i = k; i < n; i++)
        {
            for (int j = curindex; j >= 0; j--)
                adjustHeap(arr, j, maxindex);
            if(arr[0] > arr[i])
            swap(arr[0], arr[i]);
        }
        for (int i = 0; i < k; i++)
            vec[i] = arr[i];
        return vec;
    }

    //堆的一次调整为最大堆
    void adjustHeap(vector<int>& vec, int curindex,int maxindex)
    {
        int father = curindex;
        int child = 2 * father + 1;
        while (child <= maxindex)
        {
            if (child + 1 <= maxindex && vec[child + 1] > vec[child])
                child++;
            if (vec[child] > vec[father]) {
                swap(vec[child], vec[father]);
                father = child;
                child = 2 * father + 1;
            }
            else
                break;
        }
    }
};
 
快速排序法
 使用荷兰三色旗思想处理问题，设置一个flag，整个数组可分为三个部分：小于flag的、等于flag的以及大于flag的三个部分。基于以上思想，代码如下：
 
 代码如下：
 
class Solution {
public:
	pair<int, int> holandNationalFlag(vector<int>& vec, int start, int end)
	{
		int i = start - 1, j = end + 1, index = start, flag = vec[index];
		while (index < j) {
			if (vec[index] == flag)
				index++;
			else if (vec[index] > flag)
				swap(vec[index], vec[--j]);
			else
				swap(vec[index++], vec[++i]);
		}
		return make_pair(i, j);
	}
	vector<int> smallestK(vector<int>& arr, int k) {
		int start = 0, end = arr.size() - 1;
		pair<int, int> p = holandNationalFlag(arr, start, end);
		while (p.second != k)
		{
			if (p.second > k)
				end = p.second - 1;
			else if (p.second < k)
				start = p.second;
			p = holandNationalFlag(arr, start, end);
		}
		vector<int> vec;
		for (int i = 0; i < k; i++)
			vec.push_back(arr[i]);
		return vec;
	}
	
};

C语言找出数组中最小的数和它的下标，然后把它和数组中最前面的元素对换位置
 
#include <stdio.h>
int main()
{
    int A[10]={3,7,5,9,10,2,1,8,6,4};
    int i,j,t,m=A[0];
    for(i=0;i<10;i++)
    printf("%-3d",A[i]);
    putchar('\n');
    for(i=1;i<10;i++)
    {
        if(A[i]<m)
        {
            m=A[i];
            j=i;
        }
    }
    printf("The minimum is %d,它的下标是%d\n",A[j],j);
    t=A[j];
    A[j]=A[0];
    A[0]=t;
    for(i=0;i<10;i++)
    printf("%-3d",A[i]);
    return 0;
}