找到无序数组中最小的k个数

'''
快排
似乎测试结果没有出现多个最大值同时出现的情况，否则更麻烦
'''


n, k = [int(i) for i in input().strip().split()]
unsrt = [int(i) for i in input().strip().split()]

def fast_srt(unsrt):
    if len(unsrt) <= 1:
        return unsrt
    else:
        unsrta = [i for i in unsrt[1:] if i <= unsrt[0]]
        unsrtb = [i for i in unsrt[1:] if i > unsrt[0]]
        srta = fast_srt(unsrta)
        srtb = fast_srt(unsrtb)
        srt = srta + [unsrt[0]] + srtb
        return srt
        
srt = fast_srt(unsrt)
result = [str(i) for i in unsrt if i <= srt[k-1]]

print(' '.join(reesult))

#include<bits/stdc++.h>
using namespace std;
// 记录数值以及在数组中的索引
struct data{
    int val;
    int index;
};
struct cmp{
    bool operator()(data a,data b)
    {
        return a.val < b.val; //大值优先
    }
};
bool cmp2(data a,data b)
{
    return a.index < b.index;
}
int main()
{
    int n,k;
    cin>>n>>k;
    vector<data>v(n);
    for(int i=0;i<n;++i)
    {
        cin>>v[i].val;
        v[i].index = i;
    }

    // 大顶堆
    priority_queue<data,vector<data>,cmp>pq;
    for(auto item : v)
    {
        pq.push(item);
        // 维护k个元素
        if(pq.size()>k)
            pq.pop();
    }
    vector<data>ans;
    while(!pq.empty())
    {
        ans.push_back(pq.top());
        pq.pop();
    }
    // 按原索引排序
    sort(ans.begin(),ans.end(),cmp2);
    for(auto i : ans)
        cout<<i.val<<" ";
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

struct P{
    int id, x;
};

struct cmp1{
    bool operator()(P p1, P p2){
        return p1.x < p2.x;
    }
};

bool cmp2(P p1, P p2){
    return p1.id < p2.id;
}

int main(){
    int n, k, x;
    cin>>n>>k;
    vector<P> p(n), r;
    priority_queue<P, vector<P>, cmp1> q;
    for(int i=0;i<n;i++){
        cin>>p[i].x;
        p[i].id = i;
        q.push(p[i]);
        if(q.size()>k)
            q.pop();
    }
    while(!q.empty()){
        r.push_back(q.top());
        q.pop();
    }
    sort(r.begin(), r.end(), cmp2);
    for(int i=0;i<r.size();i++)
        printf("%d ", r[i].x);
    return 0;
}

package main

import (
    "container/heap"
    "fmt"
)

type IntHeap []int 

func(h IntHeap) Len() int {return len(h)}
func(h IntHeap) Less(i, j int) bool {return h[i]>h[j]}
func(h IntHeap) Swap(i,j int) {h[i],h[j] = h[j],h[i]}

func(h *IntHeap) Push(x interface{}) {
    *h = append(*h,x.(int))
}
func(h *IntHeap) Pop() interface{} {
    old := *h 
    n := len(old)
    x := old[n-1]
    *h = old[0:n-1]
    return x
}

func(h IntHeap) Peek() interface{} {
    x := h[0]
    return x
}

func main() {
    var (
        n int 
        k int 
        num int
    )
    fmt.Scan(&n,&k)
    arr := make([]int,n)
    for i:=0;i<n;i++ {
        fmt.Scan(&num)
        arr[i] = num
    }
    result := getMinKNumsByHeap(arr,k)
    for i:=0;i<len(result);i++ {
        fmt.Printf("%d ",result[i])
    }
}

func getMinKNumsByHeap(array []int, k int) []int{
    if len(array) == 0 || k < 0 || k > len(array) {
        return []int{} 
    }
    maxHeap := &IntHeap{}
    heap.Init(maxHeap)
    for i:=0;i<k;i++ {
        heap.Push(maxHeap,array[i])
    }
    for i:=k;i<len(array);i++ {
        if array[i] < maxHeap.Peek().(int) {
            heap.Pop(maxHeap)
            heap.Push(maxHeap,array[i])
        }
    }
    return *maxHeap
}

将数组排序，排序后的数组的前k个数就是最小的k个数。

import java.util.*;

public class Main{
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        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]);
        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]);
        }
                
        Arrays.sort(numArr);
        for(int i = 0;i <k;i++){
            System.out.print(numArr[i] + " ");
        }
    }
}

/*
两次STL排序
*/

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
bool comp(pair<int, int> a, pair<int, int> b) {
	return a.second < b.second;
}
int main() {
	int n, k;
	vector<pair<int, int>> buff;
	cin >> n >> k;
	for (int i = 0; i<n; i++) {
		int temp;
		cin >> temp;
		buff.push_back(make_pair(temp,i));//按<数字-位置>进行储存
	}
    //留下数字最小的前k个
	sort(buff.begin(), buff.end());
	buff.resize(k);
    //按位置排序，原序输出
	sort(buff.begin(), buff.end(), comp);
	for (auto it : buff) {
		cout << it.first << " ";
	}
	cout << endl;
	return 0;
}