import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.IOException; import java.util.PriorityQueue; import java.util.Comparator; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String[] params = br.readLine().split(" "); int n = Integer.parseInt(params[0]), k = Integer.parseInt(params[1]); String[] arr = br.readLine().split(" "); PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a); for(int i = 0; i < n; i++){ if(maxHeap.size() < k){ maxHeap.offer(Integer.parseInt(arr[i])); }else{ int cur = Integer.parseInt(arr[i]); if(maxHeap.peek() > cur){ maxHeap.poll(); maxHeap.offer(cur); } } } StringBuilder res = new StringBuilder(); while(!maxHeap.isEmpty()) res.append(maxHeap.poll() + " "); System.out.println(res.toString().trim()); } }
''' 快排 似乎测试结果没有出现多个最大值同时出现的情况,否则更麻烦 ''' 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; }