首页 > 试题广场 >

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

[编程题]输入n个整数，输出其中最小的k个

热度指数：194261 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

输入n个整数，找出其中最小的k个整数并按升序输出

本题有多组输入样例

数据范围： $1 \le n \le 1000 \$ ，输入的整数满足 $1 \le val \le 10000 \$

输入描述:

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

输出描述:

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

示例1

输入

5 2
1 3 5 7 2

输出

1 2

算法知识视频讲解

大牛吃小牛

//最大堆实现
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)

Grooovvve

写一个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)

Python3

MCh10

直接用sorted函数是排序所有，再得到前K个，如果sorted使用快速排序时间复杂度通常是Nlog_N。这个题只要前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)

Python3

半生浮名

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)

Java

苏珊树脂666

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)

tigg_ZZ

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)

奋斗ing_QT

#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)

JavaScript

blackmask88

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)

星辰大海sd

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)

Java

午·阳

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)

TheSRE

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)

牛客-120抢救中心

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)

K-_-!!623

//用小根堆完美解决
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

bool GetMinK(const vector<int> &input, int k) {     vector<int> output;     make_heap(output.begin(), output.end());     for (int i = 0; i < input.size(); i++) {         if (output.size() < k) {             output.push_back(input[i]);             push_heap(output.begin(), output.end());         }         else {             output.push_back(input[i]);             push_heap(output.begin(), output.end());             pop_heap(output.begin(), output.end());             output.pop_back();         }     }     sort_heap(output.begin(), output.end());     for (int i = 0; i < output.size() - 1; i++) {         cout << output[i] << " ";     }     cout << output[output.size() - 1] << endl;     return true;
}

int main() {     int n, k;     while (cin >> n) {         cin >> k;         vector<int> input;         for (int i = 0; i < n; i++) {             int temp;             cin >> temp;             input.push_back(temp);         }         GetMinK(input, k);     }     return 0;
}

发表于 2018-08-16 14:46:48 回复(0)

C/C++

nbgao

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <string>
#include <cmath>
#include <cctype>
#include <vector>

using namespace std;

int main()
{     int n,k;     while(cin>>n>>k)      {         vector<int> a;         for(int i=0;i<n;i++)         {             int t;             cin>>t;             a.push_back(t);         }         sort(a.begin(),a.begin()+n);         for(int i=0;i<k-1;i++)             cout<<a[i]<<" ";         cout<<a[k-1]<<endl;     }     return 0;
}

发表于 2018-06-13 01:15:23 回复(0)

Java

果子熊yeah

import java.util.*;
public class Main{
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        while(sc.hasNext()){
            int n1=sc.nextInt();
            int n2=sc.nextInt();
            int[] it=new int[n1];
            int ch=' ';
            for(int i=0;i<n1;i++){
                it[i]=sc.nextInt();
            }
            for(int i=0;i<n1-1;i++)
                for(int j=i+1;j<n1;j++)
                {
                    if (it[i]>it[j]) {
                        ch=it[i];
                        it[i]=it[j];
                        it[j]=ch;
                    }
                }
            for(int i=0;i<n2-1;i++){
                System.out.print(it[i]+" ");
            }
            System.out.println(it[n2-1]);//非常坑，最后一个要换行输出
        }
        sc.close();
    }
}

发表于 2018-04-06 17:29:11 回复(0)

C/C++

左庶长

开始也遇到了输出打印的奇奇怪怪的问题，后来看大佬们讨论，得出有几个注意点：1.最后打印时用空格隔开，最后一个元素后面没有空格；2.打印完要换行

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main()
{
    int n, m;
    while (cin>>n>>m)
    {
        vector<int> num;
        for (int i = 0; i < n; ++i)
        {
            int tmp;
            cin >> tmp;
            num.push_back(tmp);
        }
        sort(num.begin(),num.end());
        cout << num[0];
        for (int i = 1; i < m; ++i)
            cout <<" "<<num[i];
        cout << endl;
    }
    //system("pause");
    return 0;
}

发表于 2017-09-26 01:12:56 回复(1)

striving_qi

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(int argc, char *argv[])
{
    int n, k;
    int input;
    vector arr;
    while(cin>>n>>k)
    {
        arr.clear();
        for(int i = 0; i < n; i++)
        {
            cin>>input;
            arr.push_back(input);
        }
        sort(arr.begin(), arr.end());//系统里面采用的sort貌似是快排，因此照样是O(nlogn)，还可以采用小顶堆
        for(int i = 0; i < k; i++)
        {
            i == 0 ? cout << arr[i] : cout << " " << arr[i];//使用三目运算符
        }
        cout << endl;
    }
    return 0;
}

编辑于 2017-08-26 18:15:55 回复(0)

Colar

public static void main(String[] args) {
//		int[] a={1,3,5,7,2};
//		getMinK(5, 2, a);
		Scanner sc=new Scanner(System.in);
		int n=sc.nextInt();
		int k=sc.nextInt();
		int[] a=new int[n];
		for(int i=0;i<n;i++){
			a[i]=sc.nextInt();
		}
		getMinK(n, k, a);
	}
	public static boolean getMinK(int n,int k,int[] a){
		if(k>a.length||k<0){
			return false;
		}
		int start=0;
		int end=a.length-1;
		int index=partition(a,start,end);
		while(index!=(k-1)){
			if(index<(k-1)){
				start=index+1;
				index=partition(a,start,end);
			}else if(index>(k-1)){
				end=index-1;
				index=partition(a,start,end);
			}
		}
		for(int i=0;i<k;i++){
			if(i<k-1){
				System.out.print(a[i]+" ");
			}else{
				System.out.println(a[i]);
			}
			
		}
		return true;			
	}

	private static int partition(int[] a, int low, int high) {
		// TODO Auto-generated method stub
		int pivot=a[low];
		int i=low;
		int j=high;
		while(i<j){
			while(i<j&&a[j]>=pivot){
				j--;
			}
			if(i<j){
				a[i]=a[j];
				i++;
			}
			while(i<j&&a[i]<pivot){
				i++;
			}
			if(i<j){
				a[j]=a[i];
				j--;
			}
		}
		a[i]=pivot;
		return i;
	}

剑指offer上的思路，本地能通过，但提交不能通过

发表于 2017-08-24 20:43:15 回复(1)