首页 > 试题广场 >

n个数里最小的k个

[编程题]n个数里最小的k个
  • 热度指数：28860 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
找出n个数里最小的k个

输入描述:
每个测试输入包含空格分割的n+1个整数，最后一个整数为k值,n
不超过100。


输出描述:
输出n个整数里最小的k个数。升序输出
示例1

输入

3 9 6 8 -10 7 -11 19 30 12 23 5

输出

-11 -10 3 6 7
算法知识视频讲解
添加回答
C/C++
卷积神经网络哦头像 卷积神经网络哦

C++也可以很简洁 

#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;
int a[105];
int main(){
    int i = 0;
    while(scanf("%d", &a[i]) == 1) i++;
    sort(a, a + i - 1);
    for(int j = 0; j < a[i-1]; j++){
        if(j == 0) printf("%d", a[j]);
        else printf(" %d", a[j]);
    }
    printf("\n");
}
编辑于 2018-09-18 12:03:34 回复(0)
更多回答
Python
华科平凡头像 华科平凡

python 3行解法，通过测试：

a = list(map(int, input().split()))
lists, k = a[:-1], a[-1]
print(" ".join(list(map(str, sorted(lists)[:k]))))
发表于 2017-09-07 13:52:39 回复(2)
rs勿忘初心头像 rs勿忘初心 
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

//方法一：用sort排序
/*
int main()
{
	vector<int>vec;
	int x;
	while (cin >> x)
	{
		if (x == 0)
			break;
		vec.push_back(x);
	}
	sort(vec.begin(), vec.end() - 1);
	for (int i = 0; i<vec[vec.size() - 1]; i++)
		cout << vec[i] << " ";
	cout << endl;
}
*/

//方法二：用快排中的partition思想

int partition(vector<int>&vec, int start, int end)
{
	int pivot = vec[start];
	while (start<end)
	{
		while (start<end&&pivot<=vec[end])
			end--;
		vec[start] = vec[end];
		while (start<end&&pivot>=vec[start])
			start++;
		vec[end] = vec[start];
	}
	vec[start] = pivot;
	return start;
}

void GetKsmallNumber(vector<int> &vec, int k)
{
	int length = vec.size() - 1;  //总长度要除去最后一个元素k
	int start = 0, end = length - 1;
	int index = partition(vec, start, end);
	while (index != k - 1)
	{
		if (index>k - 1)
		{
			end = index - 1;
			index = partition(vec, start, end);
		}
		else
		{
			start = index + 1;
			index = partition(vec, start, end);
		}
	}
}

int main()
{
	vector<int> vec;
	int x;
	while (cin >> x)
	{
		if (x == 0)   //假设输入为0，结束while循环，因为原题目不知道vec数组的大小
			break;    //只是在VS测试要有结束条件，假设输入为0结束，做题时不需要的
		vec.push_back(x);
	}
	int k = vec[vec.size() - 1];
	GetKsmallNumber(vec, k);   //前k个数是数组中最小的K个数，但是不一定是有序的，对前k个元素用sort排序
	sort(vec.begin(), vec.begin() + 5); //对前k个元素用sort排序
	for (int i = 0; i<k; i++)
	{
		if (i<k - 1)
			cout << vec[i] << " ";  //前k个数格式：数字+空格
		else
			cout << vec[i] << endl; //第K个数格式：数字+换行
	}
}

发表于 2017-07-22 17:35:56 回复(5)
爬格子的瘦书生头像 爬格子的瘦书生 

	#include <iostream>





	#include <vector>





	#include <algorithm>





	 





	using namespace std;





	 





	intmain(){





	     





	     





	    intx;





	    vector<int>v;





	    intn;





	    while(cin>>x)





	        v.push_back(x);





	     





	    n = v.back();





	    v.pop_back();





	     





	    sort(v.begin(),v.end());





	    for(inti = 0; i < n;++i){





	        cout<<v.at(i);





	        if(i < n-1)





	            cout<<' ';





	        else





	            cout<<endl;





	         





	    }





	     





	     





	    return0;





	}

发表于 2017-04-02 18:44:54 回复(0)
多米@璟头像 多米@璟 

	import java.util.Arrays;
import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
        Scanner in=new Scanner(System.in);
        String[] string=in.nextLine().split(" ");
        int[] array=new int[string.length-1];
        for(int i=0;i<string.length-1;i++){
            array[i]=Integer.parseInt(string[i]);
        }
        Arrays.sort(array);
        for(int i=0;i<Integer.parseInt(string[string.length-1]);i++){
            System.out.print(array[i]);
            if(i!=Integer.parseInt(string[string.length-1])-1){
                System.out.print(" ");
            }
        }
    }
}
编辑于 2017-02-17 23:55:59 回复(6)
jokervsbat头像 jokervsbat
本来想用大根堆，结果题目说小于100，果断暴力解决
发表于 2017-08-23 16:07:19 回复(0)
啊咿呀嘿头像 啊咿呀嘿

PHP so easy

<?php
$str = trim(fgets(STDIN));
$arr = explode(' ', $str);
$n = array_pop($arr);
sort($arr);
$res = [];
for($i=0; $i<$n; $i++){
    $res[] = $arr[$i];
}
echo implode(" ", $res);

PHP 不使用函数，利用冒泡，排序的思路，每次将较小的往前冒泡。

<?php

$str = trim(fgets(STDIN));

$arr = explode(' ', $str);

$n = array_pop($arr);

$res = [];

for($i=0; $i<$n; $i++){
    for($j=count($arr)-1; $j>0; $j--){
        if($arr[$j] < $arr[$j-1]){
            $temp = $arr[$j];
            $arr[$j] = $arr[$j-1];
            $arr[$j-1] = $temp;
        }
    }

}

for($k=0; $k<$n; $k++){
    $res[] = $arr[$k];
}

echo implode(" ", $res);
编辑于 2017-09-10 22:25:33 回复(0)
good_coder头像 good_coder 

import java.util.Arrays;
import java.util.Scanner;

public class Main{
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while(sc.hasNext()){
			String temp = sc.nextLine();
			String[] arr = temp.split(" ");
			int[] result = new int[arr.length-1];
			int k = 0;
			for(int i=0;i<arr.length;i++){
				if(i<arr.length-1)
				result[i]=Integer.parseInt(arr[i]);
				else
				k=Integer.parseInt(arr[i]);	
			}
			Arrays.sort(result);
			for(int i=0;i<k;i++){
				if(i<k-1)
				System.out.print(result[i]+" ");
				else
					System.out.println(result[i]);
			}
		}
	}
}


发表于 2017-09-08 15:40:44 回复(1)
大向向头像 大向向 
#Python就是如此简洁
n = list(map(int,input().split(' ')))
k = n[-1]
del n[-1]
n.sort()
print(' '.join(list(map(str,n[:k]))))

发表于 2017-09-08 14:58:41 回复(0)
阿狸不是猫头像 阿狸不是猫 

	/*





	这题目重点应该是怎么样获取输入的数，这种方法掌握就可以了





	*/





	importjava.util.*;





	 





	publicclassMain{





	    publicstaticvoidmain(String args[]){





	        Scanner s= newScanner(System.in);





	        String str =s.nextLine().toString();





	        String b[]=str.split(" ");





	        intnum[] =newint[b.length-1];





	        for(inti=0;i<b.length-1;i++){





	            num[i]=Integer.parseInt(b[i]);





	        }





	        intk=Integer.parseInt(b[b.length-1]);





	        Arrays.sort(num);





	        for(inti=0;i<k;i++){





	            if(i==num.length)break;





	            System.out.print(num[i]);





	            if(i!=k-1)System.out.print(" ");





	        }





	    }





	}

发表于 2017-07-11 14:26:33 回复(2)
顾钧菲头像 顾钧菲 
import re
out_put = ""
"""
分开输入，pop记录最后一个数字并排序
python 写起来多方便 赶紧放弃java
"""
input_val = raw_input()
input_val = re.split(" ",input_val)
last_input=input_val.pop()
input_val.sort(key=int)

"""
重组输出
"""
for num in range(0,int(last_input)):
    out_put = out_put + input_val[num]+" "
out_put = out_put[:-1]
print(out_put)


发表于 2017-04-01 09:03:05 回复(0)
7_头像 7_ 

	
	

		
		

			
			
				
				

					
					
						
						

							
							

								
							


						


							

				


			

		


		

			while(line = readline()) {
		


		

			    function a(line) {
		


		

			        var arr = line.split(' ')
		


		

			        if(arr.length <= 101) {
		


		

			            var k = arr.pop()
		


		

			        arr.sort(function (a,b) {
		


		

			        return a - b
		


		

			        })
		


		

			        var newArr = []
		


		

			        for(var i = 0; i < k; i++) {
		


		

			            newArr.push(arr[i])
		


		

			    }
		


		

			        return newArr.join(' ')
		


		

			    }
		


		

			     
		


		

			        }
		


		

			        console.log(a(line))
		


		

			}
发表于 2019-03-23 23:50:39 回复(0)
Java
中南的小菜鸡头像 中南的小菜鸡 
import java.util.Scanner;
import java.util.Arrays;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            String str = sc.nextLine();
            String[] strs = str.split(" ");
            int[] nums = new int[strs.length-1];
            for(int i=0;i<strs.length-1;i++){
                nums[i]=Integer.valueOf(strs[i]);
            }
            int k = Integer.valueOf(strs[strs.length-1]);
            Arrays.sort(nums);
            for(int i=0;i<k;i++){
                System.out.print(nums[i]);
                if(i != k-1){
                    System.out.print(" ");
                }
            }
        }
    }
}

发表于 2018-10-11 19:08:09 回复(0)
C/C++
猴子居士头像 猴子居士 
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> vec;

    int num;
    while(cin >> num) {
        vec.push_back(num);
    }

    int k = vec.back();
    vec.pop_back();

    partial_sort(vec.begin(), vec.begin()+k, vec.end());
    for(int i = 0;i < k;i++) {
        i == k-1 ? cout << vec[i] << endl : cout << vec[i] << ' ';
    }

    return 0;
}
发表于 2018-08-14 11:47:06 回复(0)
C/C++
哦哦哦5头像 哦哦哦5 
//冒泡法，冒泡k次出k个最小值
#include <iostream>

using namespace std;

int main()
{
    int *n = new int[100];
    int num = 0;//数据个数
    while(cin >> n[num++]);
    num-=2;

    //冒泡
    int k = n[num];//k值
    for(int j = 0; j < k; j++)//k次冒泡
    {
        for(int i = 1; i < num - j; i++)
        {
            if(n[i-1] < n[i])
            {
                int tmp = n[i];
                n[i] = n[i-1];
                n[i-1] = tmp;
            }
        }
    }
    //输出结果
    for(int i = num - 1; i > num - 1 - k; i--)
    {
        cout << n[i];
        if(i != num - k)
            cout << " ";
    }
    
    delete []n;
    
    return 0;
}
编辑于 2018-07-28 09:56:54 回复(0)
吾生有你头像 吾生有你 
import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner input=new Scanner(System.in);
        ArrayList<Integer> list=new ArrayList<>();
        while(input.hasNext()){
            list.add(input.nextInt());
        }
        int k=list.remove(list.size()-1);
        Collections.sort(list);
        for(int i=0; i<k-1; i++){
            System.out.print(list.get(i)+" ");
        }
        System.out.println(list.get(k-1));
    }
}

_____________________________________________________________________________________________
顺手练习一下刚学会的归并排序
import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner input=new Scanner(System.in);
        ArrayList<Integer> list=new ArrayList<>();
        while(input.hasNext()){
            list.add(input.nextInt());
        }
        int[] a=new int[list.size()-1];
        for(int i=0; i<list.size()-1; i++)
            a[i]=list.get(i);
        int k=list.get(list.size()-1);
        
        sort(a, 0, a.length-1);
        for(int i=0; i<k-1; i++){
            System.out.print(a[i]+" ");
        }
        System.out.println(a[k-1]);
    }
    public static void sort(int[] a, int left, int right){
        if(left<right){
            int mid=(right+left)/2;
            sort(a, left, mid);
            sort(a, mid+1, right);
            merge(a, left, mid, right);
        }
    }
    public static void merge(int[] a, int left, int mid, int right){
        int[] b=new int[right+1];
        int index=left;
        int x=left;
        int y=mid+1;
        while(x<=mid && y<=right){
            b[index++]=(a[x]<a[y])? a[x++]:a[y++];
        }
        while(x<=mid)
            b[index++]=a[x++];
        while(y<=right)
            b[index++]=a[y++];
        for(int i=left; i<=right; i++)
            a[i]=b[i];
    }
}

编辑于 2018-05-24 10:22:55 回复(0)
C/C++
nbgao头像 nbgao 
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int partition(vector<int> &v, int l,int h)
{     int p = v[l];     while(l<h)     {         while(l<h && p<=v[h])             h--;         v[l] = v[h];         while(l<h && p>=v[l])             l++;         v[h] = v[l];     }     v[l] = p;     return l;
}

void GetKsmallest(vector<int> &v, int k)
{     int len = v.size()-1;     int l = 0, h = len-1;     int index = partition(v, l, h);     while(index != k-1)     {         if(index > k-1)         {             h = index - 1;             index = partition(v, l ,h);                 }else{             l = index + 1;             index = partition(v, l ,h);         }     }     }

int main()
{     vector<int> v;     int x;     while(cin>>x)         v.push_back(x);     int k = v[v.size()-1];     GetKsmallest(v, k);     sort(v.begin(), v.begin()+5);     for(int i=0;i<k;i++)     {         if(i==k-1)             cout<<v[i]<<endl;         else             cout<<v[i]<<" ";     }     return 0;
}

发表于 2018-01-20 01:03:53 回复(0)
牛顿的苹果头像 牛顿的苹果
import java.util.*;
public class Main{
public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        while (scan.hasNext()) {
            String str=scan.nextLine();
            String[]sc=str.split(" ");
            int[]arr=new int[sc.length];
            int[]brr=new int[sc.length-1];
            for (int i = 0; i < arr.length; i++) {
                arr[i] = Integer.valueOf(sc[i]);
                for (int j = 0; j < arr.length-1; j++) {
                    brr[j]=arr[j];
                }
            }
            int n=arr[arr.length-1];
            Arrays.sort(brr);
            for (int i = 0; i < n; i++) {
                System.out.print(brr[i]);
                if (i!=n-1) {
                    System.out.print(" ");
                }
            }
            
            
        }
        
    }
}
代码思路很简单，主要是对最后一个数字进行判断

发表于 2018-01-01 14:47:11 回复(0)
顾翅头像 顾翅

用stringstream做输入，然后一个Map解决的事情 

#include<iostream>
#include<map>
#include<string>
#include<sstream>
using namespace std;

int main(){
    map<int,int> table;
    map<int, int>::iterator it;
    int cur, index = 0;
    string s;
    getline(cin, s);
    stringstream ss;
    ss << s;
    while (!ss.eof()){
        ss >> cur;
        if (!(table.find(cur)==table.end()))
            table[cur]++;
        else
            table.insert(pair<int, int>(cur, 1));

    }
    if (table[cur] > 1)
        table[cur]--;
    else
        table.erase(cur);//最后一个数为k，所以要从map里删除
    it = table.begin();
    for (int i = 0; i < cur;){
        while (it->second--){
            if(i==cur-1)
                cout<<it->first;
            else
                cout << it->first<<" ";
            i++;
        }
        it++;
    }

}
编辑于 2017-12-06 10:14:10 回复(0)
ACpeppermint头像 ACpeppermint
一看 n 才 100， 直接快排得了。 

	#include <iostream>





	#include <algorithm>





	#include <sstream>





	





	using namespace std;





	





	const int maxn = 105;





	string p;





	int arr[maxn];





	





	int main()





	{





	    getline(cin, p);





	    stringstream ss;





	    ss << p;





	    int n = 0;





	    int k;





	    while(!ss.eof()) {





	        ss >> arr[n++];





	    }





	    k = arr[n - 1];





	    sort(arr, arr + n - 1);





	    for(int i = 0; i < k; i++) {





	        cout << arr[i];





	        i != k - 1 ? cout << " " : cout << endl;





	    }





	    return 0;





	}

发表于 2017-09-20 09:23:22 回复(0)
提交观点

问题信息

C++工程师 2017 好未来 排序 Java工程师
难度：
145条回答 17891浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号