输入n个整数,找出其中最小的k个整数并按升序输出
本题有多组输入样例
数据范围: ,输入的整数满足
#include <iostream> #include <queue> using namespace std; int main(){ int n; int k; cin>>n>>k; priority_queue<int> pq; vector<int> num(n,0); vector<int> res(k,0); for(int i=0;i<n;++i){ cin>>num[i]; if(i<k) pq.emplace(num[i]); else if(num[i]<pq.top()){ pq.pop(); pq.emplace(num[i]); } } for(int i=k-1;i>=0 && !pq.empty();--i){ res[i]=pq.top(); pq.pop(); } for(int m:res) cout<<m<<" "; return 0; }
import java.util.ArrayList; import java.util.Collections; import java.util.List; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); while (sc.hasNext()) { int n = sc.nextInt(), k = sc.nextInt(); List<Integer> list = new ArrayList<>(n); while (n-- > 0) list.add(sc.nextInt()); Collections.sort(list); StringBuilder sb = new StringBuilder(); for (int i = 0; i < k; i++) sb.append(list.get(i)).append(" "); System.out.println(sb.toString().trim()); } sc.close(); } }
#include <algorithm> #include <iostream> #include <vector> using namespace std; int main() { int n, k, tmp; while (cin >> n >> k) { vector<int> v; while (n-- && cin >> tmp) v.push_back(tmp); sort(v.begin(), v.end()); string result; for (int i = 0; i < k; i++) { result += to_string(v[i]) + (i == k - 1 ? "" : " "); } cout << result << endl; } return 0; }
#include <stdio.h> #include <stdlib.h> int main() { int n, k; while (scanf("%d %d", &n, &k) != EOF) { int *p = calloc(n, sizeof(int *)); for (int i = 0; i < n; i++) scanf("%d", p + i); for (int i = 1; i < n; i++) { for (int j = 0; j < i; j++) { if (*(p + i) < *(p + j)) { int tmp = *(p + i); *(p + i) = *(p + j); *(p + j) = tmp; } } } for (int i = 0; i < k; i++) printf((i == k - 1) ? "%d\n" : "%d ", *(p + i)); free(p); } return 0; }
//自己纯手工打造的最小堆呀 #include<iostream> #include<vector> using namespace std; void heapify(vector<int>&A, int n, int i){//堆化,以A[i]为堆顶开始堆化,即对下标为i的数据进行堆化,n为数组中数据的个数 if (n >= A.size()){return;}//数组下标是1...n,所以n < A.size(); while (true){ int maxPos = i;//maxPos最终为父节点和孩子节点中数值最小的节点的index。 if (2 * i <= n && A[maxPos] > A[2 * i])maxPos = 2 * i; if (2 * i + 1 <= n && A[maxPos] > A[2 * i + 1])maxPos = 2 * i + 1; if (maxPos == i)break;//父节点比孩子节点都小,堆化结束 swap(A[i], A[maxPos]); i = maxPos; } } void buildHeap(vector<int>&B, int n){//对无序数组B进行堆化,对下标从n/2到1的数据进行堆化,使其成为一个最小堆,建堆的时间复杂度为O(n) if (n >= B.size()){return;} //数组下标是1...n,所以n < A.size(); //下标为n/2的节点是第一个非叶子节点。 //因为叶子节点往下只能自己跟自己比较,所以我们直接从第一个非叶子节点开始,依次堆化 for (int i = n / 2; i >= 1; i--){ heapify(B, n, i); } } void removeMin(vector<int>&A,int& count){//删除堆顶元素,使剩下的元素依然为最小堆,这是自上到下的堆化调节方式 if (count == 0)return; A[1] = A[count];//A[0]不存储任何数据,用最后一个数来填补删除掉的最大数,然后进行对话处理 --count; heapify(A, count, 1); } int main(){ int n1,n2; while(cin>>n1>>n2){ vector<int> buf(n1+1,0); for(int i = 0; i < n1; i++){ cin>>buf[i+1]; } int count = n1; buildHeap(buf,count); cout<<buf[1]; for(int i = 1; i < n2; i++){ removeMin(buf,count); cout<<" "<<buf[1]; } cout<<endl; } system("pause"); return 0; }
#include <bits/stdc++.h> using namespace std; int main() { int n,k; while(cin>>n>>k) { vector<int> dp(n); for(int i=0;i<n;i++) { cin>>dp[i]; } sort(dp.begin(),dp.end()); for(int i=0;i<k-1;i++) cout<<dp[i]<<" "; cout<<dp[k-1]<<endl; } return 0; }
import java.util.*; public class Main{ public static void main(String[] args){ Scanner sc = new Scanner(System.in); while(sc.hasNext()){ int m = sc.nextInt(); int n = sc.nextInt(); int[] nums = new int[m]; for(int i=0; i<m; i++){ nums[i] = sc.nextInt(); } heapSort(nums, n); } } private static void heapSort(int[] nums, int key){ int n = nums.length; for(int i=n/2-1; i>=0; i--) heapify(nums, i, n); for(int i=n-1; i>=n-key; i--){ if(i != n-key) System.out.print(nums[0]+" "); else System.out.print(nums[0]); int temp = nums[i]; nums[i] = nums[0]; nums[0] = temp; heapify(nums, 0, i); } } private static void heapify(int[] nums, int i, int n){ int smallest = i; int l = 2*i+1; int r = 2*i+2; if(l<n && nums[l]<nums[smallest]) smallest = l; if(r<n && nums[r]<nums[smallest]) smallest = r; if(smallest != i){ int temp = nums[i]; nums[i] = nums[smallest]; nums[smallest] = temp; heapify(nums, smallest, n); } } }对于测试用例用例:
//最大堆实现
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (sc.hasNext()) {
int len=sc.nextInt();
int k=sc.nextInt();
int[] nums=new int[len];
for (int i = 0; i <len ; i++) {
nums[i]=sc.nextInt();
}
PriorityQueue<Integer> q=new PriorityQueue<>(new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o2-o1;
}
});
for (int i = 0; i <len ; i++) {
if(i<k){
q.offer(nums[i]);
}else{
if(nums[i]<q.peek()){
q.poll();
q.offer(nums[i]);
}
}
}
ArrayList<Integer> list=new ArrayList<>();
while(!q.isEmpty()){
list.add(q.poll());
}
for(int i=list.size()-1;i>0;i--){//按顺序
System.out.print(list.get(i)+" ");
}
System.out.println(list.get(0));//有多个测试用例 最后换行 代表结束
}
}
}
#include <iostream> #include <algorithm> using namespace std; bool cmp(int a, int b){ return a<b; } bool GetMinK(unsigned int uiInputNum, int pInputArray[], unsigned int uiK, int ** pOutputArray){ if(uiInputNum<uiK) return false; sort(pInputArray,pInputArray+uiInputNum,cmp); *pOutputArray = new int[uiK]; for(unsigned int i=0;i<uiK;i++){ (*pOutputArray)[i] = pInputArray[i]; } return true; } int main(){ unsigned int n,k; while(cin>>n>>k){ int arr[n]; for(int i=0;i<n;i++){ cin>>arr[i]; } int * OutputArr =nullptr; if(GetMinK(n,arr,k,&OutputArr)){ for(unsigned int i=0;i<k-1;i++){ cout<<OutputArr[i]<<" "; } cout<<OutputArr[k-1]<<endl; delete [] OutputArr; } } return 0; }
def func(num, k): for i in range(k): min_idx = i min_value = num[i] for j in range(i+1, len(num)): if num[j] < min_value: min_idx = j min_value = num[j] num[i], num[min_idx] = num[min_idx], num[i] result = [str(i) for i in num[:k]] print(" ".join(result)) def mian(): try: while True: m, k = map(int, input().strip().split(" ")) num = input().strip().split(" ") num = [int(i) for i in num] func(num, k) except: pass if __name__ == "__main__": mian()
import java.util.Scanner; import java.util.Arrays; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(), k = sc.nextInt(); int[] list = new int[n]; for (int i = 0; i < n; i++) { list[i] = sc.nextInt(); } String orderedStr = subArr(list, k); System.out.println(orderedStr); } public static String subArr(int[] arr, int len) { Arrays.sort(arr); StringBuilder subStr = new StringBuilder(); for (int i = 0; i < len; i++) { subStr.append(arr[i]).append(" "); } return subStr.toString(); } }
import java.util.*; public class Main{ public static void main(String[] args){ Scanner scanner = new Scanner(System.in); while (scanner.hasNextInt()){ int n = scanner.nextInt(); int k = scanner.nextInt(); List<Integer> numbers = new ArrayList<>(); for (int i = 0; i < n; i++){ numbers.add(scanner.nextInt()); } Collections.sort(numbers); StringBuilder result = new StringBuilder(); for (Integer num : numbers.subList(0,k)){ result.append(String.valueOf(num) + " "); } System.out.println(result.toString()); } } }
#include <stdio.h> int main(){ int count = 0; while(scanf("%d", &count)!=EOF){ int k = 0; scanf("%d\n", &k); int arr[1000] = {0}; for(int i=0;i<count;i++){ scanf("%d", &arr[i]); } for(int i=0;i<count;i++){ for(int j=0;j<(count-1);j++){ if(arr[i]<arr[j]){ int t = arr[i]; arr[i] = arr[j]; arr[j] = t; } } } for(int i=0;i<(k-1);i++){ printf("%d ", arr[i]); } printf("%d\n", arr[k-1]); } return 0; }
while(line = readline()) { let requirement = line.split(' '); let total = parseInt(requirement[0]); let outputCount = parseInt(requirement[1]); let inputArr = readline().split(' '); let toInt = []; for (let i = 0; i < total; i++) { toInt.push(parseInt(inputArr[i])); }; toInt.sort((a, b) => { return a - b; }); console.log(toInt.slice(0, outputCount).join(' ')); };
import java.util.*; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); while (scanner.hasNext()) { int n = scanner.nextInt(); int k = scanner.nextInt(); int[] a = new int[n]; for (int i = 0; i < n; i++) { a[i] = scanner.nextInt(); } // 排序 Arrays.sort(a); // 输出 for (int i = 0; i < k; i++) { System.out.print(a[i]+" "); } System.out.println(); } } }
import java.util.*; public class Main{ public static void main(String []args){ Scanner sc = new Scanner(System.in); while(sc.hasNext()){ int n = sc.nextInt(); int k = sc.nextInt(); List<Integer> list = new ArrayList<Integer>(); while(n > 0){ list.add(sc.nextInt()); n--; } Collections.sort(list); for(int i=0; i<k; i++){ System.out.print(list.get(i)+" "); } System.out.println(" "); } } }
//蛮简单的,直接输入到数组中排个序就好 #include<iostream> #include<algorithm> using namespace std; int main(){ int n,count; while(cin>>n){ cin>>count; int* a=new int[n]; for(int i=0;i<n;i++) cin>>a[i]; sort(a,a+n); for(int i=0;i<count;i++) cout<<a[i]<<" "; cout<<endl; } return 0; }
import java.math.BigInteger; import java.util.*; public class Main{ public static void main(String[] args) { Scanner sc = new Scanner(System.in); while(sc.hasNext()){ int n = sc.nextInt(); int need = sc.nextInt(); int[] array = new int[n]; for(int i=0; i<n; i++) { array[i] = sc.nextInt(); } Arrays.sort(array); for(int i=0; i<need; i++) { System.out.print(array[i]+" "); } System.out.println(); } } }