[编程题]n个数里最小的k个
除了sort以外，也可以用minheap解决，但是要额外空间
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
// while (in.hasNext()) {
String str = in.nextLine();
String[] strs = str.split(" ");
int n = strs.length;
int k = Integer.valueOf(strs[n - 1]);
int[] nums = new int[n - 1];
for (int i = 0; i < n - 1; i++) {
nums[i] = Integer.valueOf(strs[i]);
}
PriorityQueue<Integer> minheap = new PriorityQueue<Integer>();
int[] result = new int[k];
for (int i = 0; i < n - 1; i++) {
minheap.offer(nums[i]);
}
for (int i = 0; i < k; i++) {
System.out.print(minheap.poll() + " ");
}
// }
}
}
发表于 2024-11-07 09:14:17
回复(0)
- 排序自己只会插入、选择、冒泡三种，这里直接用工具类来排了
import java.util.*;
public class Main
{
public static void main(String [] args)
{
Scanner sc=new Scanner(System.in);
while(sc.hasNextLine())
{
String str=sc.nextLine();
String [] arr=str.split(" ");
int [] arr2=new int[arr.length-1];
for(int i=0;i<arr.length-1;i++)
{
arr2[i]=Integer.parseInt(arr[i]);
}
int n=Integer.parseInt(arr[arr.length-1]);
Arrays.sort(arr2);
for(int i=0;i<n;i++)
{
if(i==n-1)
{
System.out.print(arr2[i]);
}
else
{
System.out.print(arr2[i]+" ");
}
}
}
}
}
发表于 2020-03-28 16:37:22
回复(0)
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)
public class Main {
public static void main(String[] args) {
Scanner scan=new Scanner(System.in);
String line = scan.nextLine();
String[] sp = line.split(" ");
String n = sp[sp.length-1];
int [] num=new int[sp.length-1];
for (int i = 0; i < sp.length-1; i++) {
num[i]=Integer.parseInt(sp[i]);
}
Arrays.sort(num, 0, num.length);
String res="";
for (int i = 0; i < Integer.parseInt(n); i++) {
res+=num[i]+" ";
}
String result=res.trim();
System.out.println(result);
}
}
public static void main(String[] args) {
Scanner scan=new Scanner(System.in);
String line = scan.nextLine();
String[] sp = line.split(" ");
String n = sp[sp.length-1];
int [] num=new int[sp.length-1];
for (int i = 0; i < sp.length-1; i++) {
num[i]=Integer.parseInt(sp[i]);
}
Arrays.sort(num, 0, num.length);
String res="";
for (int i = 0; i < Integer.parseInt(n); i++) {
res+=num[i]+" ";
}
String result=res.trim();
System.out.println(result);
}
}
发表于 2018-10-01 20:18:09
回复(0)
先读取输入的数据，然后转换成string数组，取出string数组的最后一个数字，赋给一个int，然后将string转换成string.length-1长度的int数组，排序比较。
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
public class Main {
public static void main(String[]args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
String[] Str = bf.readLine().split(" ");
int mm = Integer.parseInt(Str[Str.length-1]);
int [] nn = new int[Str.length-2];
for (int i = 0; i < Str.length-2; i++) {
nn[i] = Integer.parseInt(Str[i]);
}
Arrays.sort(nn);
StringBuffer sBuffer = new StringBuffer();
for (int i = 0; i < mm; i++) {
sBuffer.append(String.valueOf(nn[i])+" ");
}
System.out.println(sBuffer.toString().trim());
}
}
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
public class Main {
public static void main(String[]args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
String[] Str = bf.readLine().split(" ");
int mm = Integer.parseInt(Str[Str.length-1]);
int [] nn = new int[Str.length-2];
for (int i = 0; i < Str.length-2; i++) {
nn[i] = Integer.parseInt(Str[i]);
}
Arrays.sort(nn);
StringBuffer sBuffer = new StringBuffer();
for (int i = 0; i < mm; i++) {
sBuffer.append(String.valueOf(nn[i])+" ");
}
System.out.println(sBuffer.toString().trim());
}
}
发表于 2018-09-11 19:22:31
回复(0)
import java.util.Scanner;
public class Main{
public static void main(String[] args){
Scanner s = new Scanner(System.in);
String str = s.nextLine();
String[] str2 = str.split(" ");
int[] int1 = new int[str2.length-1];
for(int i = 0 ; i< str2.length-1 ;i++){
int1[i] = Integer.parseInt(str2[i]);
}
for(int j =0; j<int1.length-1;j++){
for(int i =0 ; i<int1.length-1;i++){
if(int1[i]>int1[i+1]){
int k = int1[i];
int1[i] = int1[i+1];
int1[i+1] = k;
}
}
}
int i = 0;
for (; i < Integer.parseInt(str2[str2.length-1])-1; i++){
System.out.print(int1[i]);
System.out.print(" ");
}
System.out.print(int1[i]);
}
}
发表于 2018-07-29 15:38:39
回复(0)
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
String str = sc.nextLine();
String[] arr = str.trim().split(" ");
int k = Integer.parseInt(arr[arr.length - 1]);
int len = arr.length - 1;
int[] nums = new int[len];
for (int i=0; i<len; i++)
{
nums[i] = Integer.parseInt(arr[i]);
}
Arrays.sort(nums);
for (int i=0; i<k; i++)
{
System.out.print(nums[i]);
if (i < k-1)
System.out.print(" ");
else
System.out.print("\n");
}
}
}
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
String str = sc.nextLine();
String[] arr = str.trim().split(" ");
int k = Integer.parseInt(arr[arr.length - 1]);
int len = arr.length - 1;
int[] nums = new int[len];
for (int i=0; i<len; i++)
{
nums[i] = Integer.parseInt(arr[i]);
}
Arrays.sort(nums);
for (int i=0; i<k; i++)
{
System.out.print(nums[i]);
if (i < k-1)
System.out.print(" ");
else
System.out.print("\n");
}
}
}
发表于 2018-03-02 14:49:06
回复(0)
//最小堆实现的优先队列
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int count = 0;
int[] array = new int[101];
while (in.hasNext())
array[count++] = in.nextInt();
int k = array[count - 1];
PriorityQueue<Integer> min = new PriorityQueue<>();
for (int i = 0; i < count - 1; i++)
min.offer(array[i]);
for (int i = 0; i < k; i++) {
if (i < k - 1)
System.out.print(min.poll() + " ");
else
System.out.println(min.poll());
}
}
}
---------------------------------------------------------------
//修改输入数据获取的方式
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
String string = in.nextLine();
String[] strings = string.split("\\s+");
int k = Integer.parseInt(strings[strings.length - 1]);
int[] array = new int[strings.length - 1];
for (int i = 0; i < strings.length - 1; i++)
array[i] = Integer.parseInt(strings[i]);
Arrays.sort(array);
for (int i = 0; i < k; i++) {
if (i < k - 1)
System.out.print(array[i] + " ");
else
System.out.println(array[i]);
}
}
}
编辑于 2017-12-26 16:12:05
回复(0)
import java.util.Scanner; public class Main { public static void main(String args[]) { Scanner scanner = new Scanner(System.in); while (scanner.hasNext()) { String[] numbers = scanner.nextLine().split(" "); int n = numbers.length - 1; int k = Integer.parseInt(numbers[n]); String temp; int m = 0; for (int j = n - 1; j >= 0; j--) { for (int i = j; i >= 1; i--) { if (Integer.parseInt(numbers[i]) < Integer.parseInt(numbers[i - 1])) { temp = numbers[i - 1]; numbers[i - 1] = numbers[i]; numbers[i] = temp; } } } for (int i = 0; i < k - 1; i++) { System.out.print(numbers[i]); System.out.print(" "); } System.out.print(numbers[k - 1]); } } }这个题就是一个不完全的冒泡排序就可以解决，把所有输入的数字放到一个数组里面，最后一个数字是k值，不参与排序，把最小的k个按照从小到大的顺序依次冒泡到前面，然后输出即可
发表于 2017-12-03 10:32:06
回复(0)
import java.util.Arrays;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String[] strArr = sc.nextLine().split(" +");
sc.close();
int[] arr = new int[strArr.length-1];
for (int i = 0; i < arr.length; i++) {
arr[i] = Integer.parseInt(strArr[i]);
}
int k = Integer.parseInt(strArr[strArr.length-1]);
Arrays.sort(arr);
for (int i = 0; i < k; i++) {
if(i == k-1)
System.out.println(arr[i]);
else
System.out.print(arr[i]+" ");
}
}
}
发表于 2017-11-16 11:21:14
回复(0)
import java.util.ArrayList;
import java.util.Collections;
import java.util.PriorityQueue;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
ArrayList<Integer> list = new ArrayList<>();
while (cin.hasNextInt()) {
int cur = cin.nextInt();
list.add(cur);
}
int k = list.remove(list.size() - 1);
Collections.sort(list);
for (int i = 0; i < k; i++) {
if (i != 0)
System.out.print(" ");
System.out.print(list.get(i));
}
}
}
发表于 2017-09-06 01:21:25
回复(0)
import java.util.*;
public class Main{
public static void main(String[] args) {
@SuppressWarnings("resource")
Scanner in=new Scanner(System.in);
String[] inputStr = in.nextLine().split(" ");
int n = inputStr.length;
int[] data = new int[n-1];
for(int i=0;i<n-1;i++){
data[i] = Integer.valueOf(inputStr[i]);
}
int k = Integer.valueOf(inputStr[n-1]);
Arrays.sort(data);
for(int j=0 ;j<k-1; j++){
System.out.print(data[j]+" ");
}
System.out.println(data[k-1]);
}
}
发表于 2017-08-24 13:46:17
回复(0)
//由于本题要求输出的最小的k个数是升序排列，所以使用最小堆
import java.util.*;
public class Main{
//调整以下标i的结点为根节点的堆
public static void minHeapify(int [] A, int i, int minHeapSize){
int l = 2*i + 1;//左孩子下标
int r = 2*i + 2;//右孩子下标
int largest = 0;//根节点，左右孩子中结点最小的下标
if(l < minHeapSize && A[i]>A[l]){
largest = l;
}else{
largest = i;
}
if(r < minHeapSize && A[largest] > A[r]){
largest = r;
}
if(largest != i){
int temp = A[i];
A[i] = A[largest];
A[largest] = temp;
minHeapify(A,largest,minHeapSize);
}
}
//构建最小堆
public static void buildMinHeap(int []A){
int minHeapSize = A.length;
for(int i=(minHeapSize/2-1) ; i>=0; --i){
minHeapify(A,i,minHeapSize);
}
}
//获取最小的k个数
public static void getSmallKNum(int []A, int k){
int minHeapSize = A.length;
buildMinHeap(A);
for(int i=A.length-1; i>0; --i){
if(k == 0) break;
int temp = A[0];
A[0] = A[i];
A[i] = temp;
minHeapSize--;
k--;
minHeapify(A,0,minHeapSize);
}
}
//主程序
public static void main(String[] args){
//数据输入
Scanner in = new Scanner(System.in);
String[] s = in.nextLine().split(" ");
int []A = new int[s.length-1];
int k = 0;
for (int i=0; i<s.length; ++i){
if(i < s.length-1){
A[i] = Integer.parseInt(s[i]);
}else{
k = Integer.parseInt(s[i]);
}
}
//获取最小的k个数，从数组A末尾向前数k个即为升序的最小的k个数
getSmallKNum(A,k);
//按要求打印
for(int i=A.length-1; i> A.length-k ; --i){
System.out.print(A[i] + " ");
}
System.out.println(A[A.length-k]);
}
}
编辑于 2017-08-20 10:40:48
回复(0)
问题信息
难度：
14条回答
107收藏
18925浏览
通过挑战的用户
查看代码-
2022-11-14 16:23:00 -
2022-09-07 11:22:45
-
2022-08-31 21:19:59 -
2022-08-29 10:29:17
-
2022-08-26 19:55:07
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
