首页 > 试题广场 >

输入n个整数,输出其中最小的k个

[编程题]输入n个整数,输出其中最小的k个
  • 热度指数:179813 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解
输入n个整数,找出其中最小的k个整数并按升序输出

本题有多组输入样例

数据范围: ,输入的整数满足

输入描述:

第一行输入两个整数n和k
第二行输入一个整数数组



输出描述:

从小到大输出最小的k个整数,用空格分开。

示例1

输入

5 2
1 3 5 7 2

输出

1 2
C++ 大根堆
#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;
}


发表于 2022-03-10 15:44:03 回复(0)
这题目就是考集合排序:

Java:
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();
    }
}
 
C++:
#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;
}

C:
#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;
}



编辑于 2021-01-25 17:28:54 回复(1)
//自己纯手工打造的最小堆呀
#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;
}

发表于 2019-07-18 22:30:34 回复(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;
}

发表于 2018-08-20 13:02:03 回复(3)
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);
        }
    }
}

对于测试用例用例:
445 237 1886 8470 3020 7940 5617 9627 3976 3571 9176 9248 812 2909 4788 1521 562 8325 8829 8196 5615 4498 9185 8421 5297 5511 6334 6030 5302 186 5106 5213 8195 4412 1927 6359 7245 1462 5080 6318 1649 980 3159 3768 8958 6946 5940 5976 8717 8176 3367 8574 1024 6103 782 8300 1511 3183 5259 6038 8416 9249 5163 9586 2434 3193 6288 276 1210 4124 598 3951 7678 5128 5277 8355 1873 48 2256 8683 725 6527 6969 195 3762 2132 2946 4260 5115 6412 1773 1833 9128 4907 6496 316 1876 1831 9252 1193 8247 5626 612 9081 3606 6590 6543 9363 7310 3631 5962 3758 8372 3472 4062 5962 2522 5853 7124 2323 7753 2893 4350 6510 6543 3817 9310 4503 554 9473 8672 17 2075 4808 277 6389 4177 3296 6018 2916 1281 5486 252 2 8951 1476 1899 2587 6967 3611 451 4886 3243 3974 7765 7454 2356 4831 454 64 1454 3486 6272 6418 8060 5435 4396 4762 6668 2422 8690 6720 416 9484 28 8798 5546 7566 1733 3916 6448 4430 7476 6442 355 8329 1645 3491 1002 4086 254 227 3520 2517 2237 7972 4782 2606 9021 1518 8945 6761 7920 3227 3743 3973 7354 3444 6914 3397 8893 8604 2824 2421 8610 7500 939 1263 1496 4443 4874 9248 2150 5980 8295 6449 735 7849 8553 5551 6906 8074 9224 2990 265 5396 7314 2982 6576 4326 8817 2811 9358 1672 577 6297 9475 7671 2185 2928 8084 3801 292 3069 7479 8979 5312 3717 4241 2764 4003 6839 358 3437 6240 6647 8952 5455 7540 7312 742 6201 6147 926 9028 1281 8855 1549 3540 9144 3218 8318 6024 5031 9025 4055 8392 8602 4421 4600 19 1035 3864 6954 5162 8848 6216 3331 3388 6669 7760 50 4014 1920 2536 7554 2528 7450 7299 2241 7769 7603 6613 1790 5325 5276 6609 9476 3994 2985 3293 5493 3310 3497 2329 6159 3969 7391 5920 8409 8181 2431 5930 5713 9087 8389 9112 9252 6488 6831 2496 2338 6568 5861 8308 2168 5319 3691 1350 5383 6629 7243 5147 9587 1106 116 4374 7730 4597 7695 9433 4467 5367 5602 5102 89 4012 7802 3193 2900 7399 811 8391 1288 8704 3647 6900 4343 8478 55 5218 8716 7361 1859 4340 9548 6010 7719 3280 9453 387 4849 2840 3029 7307 7147 8684 8819 2577 2584 2871 7011 4299 4134 9600 8196 1371 9161 4305 4095 4457 8408 3663 9111 8473 3176 7235 9333 7948 5503 1866 2771 4411 313 5972 5359 8919 5368 4315 2937 9061 4467 2989 8520 434 7667 5337 6394 4737 4873 4324 6764 6341 6722 5710 9403 3241
对应输出应该为:
2 17 19 28 48 50 55 64 89 116 186 195 227 252 254 265 276 277 292 313 316 355 358 387 416 434 451 454 554 562 577 598 612 725 735 742 782 811 812 926 939 980 1002 1024 1035 1106 1193 1210 1263 1281 1281 1288 1350 1371 1454 1462 1476 1496 1511 1518 1521 1549 1645 1649 1672 1733 1773 1790 1831 1833 1859 1866 1873 1876 1886 1899 1920 1927 2075 2132 2150 2168 2185 2237 2241 2256 2323 2329 2338 2356 2421 2422 2431 2434 2496 2517 2522 2528 2536 2577 2584 2587 2606 2764 2771 2811 2824 2840 2871 2893 2900 2909 2916 2928 2937 2946 2982 2985 2989 2990 3020 3029 3069 3159 3176 3183 3193 3193 3218 3227 3241 3243 3280 3293 3296 3310 3331 3367 3388 3397 3437 3444 3472 3486 3491 3497 3520 3540 3571 3606 3611 3631 3647 3663 3691 3717 3743 3758 3762 3768 3801 3817 3864 3916 3951 3969 3973 3974 3976 3994 4003 4012 4014 4055 4062 4086 4095 4124 4134 4177 4241 4260 4299 4305 4315 4324 4326 4340 4343 4350 4374 4396 4411 4412 4421 4430 4443 4457 4467 4467 4498 4503 4597 4600 4737 4762 4782 4788 4808 4831 4849 4873 4874 4886 4907 5031 5080 5102 5106 5115 5128 5147 5162 5163 5213 5218 5259 5276 5277 5297 5302 5312 5319 5325 5337 5359 5367
你的输出为:
2 17 19 28 48 50 55 64 89 116 186 195 227 252 254 265 276 277 292 313 316 355 358 387 416 434 451 454 554 562 577 598 612 725 735 742 782 811 812 926 939 980 1002 1024 1035 1106 1193 1210 1263 1281 1281 1288 1350 1371 1454 1462 1476 1496 1511 1518 1521 1549 1645 1649 1672 1733 1773 1790 1831 1833 1859 1866 1873 1876 1886 1899 1920 1927 2075 2132 2150 2168 2185 2237 2241 2256 2323 2329 2338 2356 2421 2422 2431 2434 2496 2517 2522 2528 2536 2577 2584 2587 2606 2764 2771 2811 2824 2840 2871 2893 2900 2909 2916 2928 2937 2946 2982 2985 2989 2990 3020 3029 3069 3159 3176 3183 3193 3193 3218 3227 3241 3243 3280 3293 3296 3310 3331 3367 3388 3397 3437 3444 3472 3486 3491 3497 3520 3540 3571 3606 3611 3631 3647 3663 3691 3717 3743 3758 3762 3768 3801 3817 3864 3916 3951 3969 3973 3974 3976 3994 4003 4012 4014 4055 4062 4086 4095 4124 4134 4177 4241 4260 4299 4305 4315 4324 4326 4340 4343 4350 4374 4396 4411 4412 4421 4430 4443 4457 4467 4467 4498 4503 4597 4600 4737 4762 4782 4788 4808 4831 4849 4873 4874 4886 4907 5031 5080 5102 5106 5115 5128 5147 5162 5163 5213 5218 5259 5276 5277 5297 5302 5312 5319 5325 5337 5359 536756 127 215 357 735 873 919 1007 1034 1056 1103 1219 1221 1350 1449 1550 1733 1744 2015 2448 2507 2538 2747 2767 2875 3072 3209 3333 3378


为什么我本地测试是对的,但是牛客上不是呢?
发表于 2020-03-26 18:18:04 回复(5)
//最大堆实现
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));//有多个测试用例 最后换行 代表结束 
        }
    }
}

发表于 2020-03-17 21:20:38 回复(1)
写一个new/delete,指向指针的指针实现的。
注意最后一定要换行;
#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;
}


发表于 2020-02-19 00:18:55 回复(1)
直接用sorted函数是排序所有,再得到前K个,如果sorted使用快速排序时间复杂度通常是NlogN这个题只要前K个,因此利用选择排序,外层只循环K步即可,时间复杂度为K*N。
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()
发表于 2021-12-12 22:42:21 回复(0)
while True:
    try:
        n, k = map(int, input().split(' '))
        li = input().strip().split(' ')
        print(' '.join(sorted(li)[:k]))
    except:
        break
发表于 2022-05-25 21:55:50 回复(2)
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();
    }
}

发表于 2022-04-13 16:09:50 回复(0)
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());
        }
    }
}

发表于 2021-01-19 00:14:13 回复(0)
#include <iostream>
#include <algorithm>

using namespace std;
int main()
{
    int n,k;
    while(cin>>n>>k)
    {
        int st[n];
        for(int i=0;i<n;i++)
        {
            cin >> st[i];
        }
        sort(st,st+n);
        for(int i=0;i<k;i++)
            cout << st[i] << ' ';
        cout << endl;     //不加这个用例过不了。。。。
    }
    return 0;
}

发表于 2020-08-26 10:22:34 回复(0)
#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;
}

发表于 2020-07-12 23:23:34 回复(0)
#include <bits/stdc++.h>
using namespace std;
int main(){
    for(int n,k;cin>>n>>k;){
        vector<int> vec(n);
        for(auto &i:vec) cin>>i;
        stable_sort(vec.begin(), vec.end());
        for(int i=0;i<k;++i) cout << vec[i] << ' ';
        cout << endl;
    }
}

    😑
发表于 2020-06-27 12:35:42 回复(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(' '));
};

编辑于 2020-06-15 20:52:11 回复(0)
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();
        }
    }
}

发表于 2020-04-21 20:04:29 回复(0)
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(" ");
        }
    }
}

发表于 2020-03-20 13:49:38 回复(0)
//蛮简单的,直接输入到数组中排个序就好
#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;
}

发表于 2020-01-07 20:47:51 回复(0)
while True:
    try:
        count, k = input().strip().split()
        print(" ".join([ str(j) for j in sorted([int(i) for i in input().strip().split()])[:int(k)]]))
    except:
        raise

发表于 2019-11-19 23:18:02 回复(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();
        }
    }
}

发表于 2018-10-06 22:07:48 回复(0)