2 xuanjimingyue xuanjimingyue 于 2016.02.08 15:58 提问

JAVA排序问题求若干个数的数组中第k个最大值

代码:
import java.util.Scanner;
public class Sorting0{
public int[] sort(int[] num){
for(int i=0;i<num.length;i++){

        for(int j=0;j<num.length-i-1;j++){

            if(num[j]<num[j+1]){

                int n=0;
                n=num[j];
                num[j]=num[j+1];
                num[j+1]=n;
            }
        }
    }
    return num;
}
public static void main(String[] args){
    Scanner input=new Scanner(System.in);
    int k=input.nextInt();
    Sorting0 s=new Sorting0();
    int[] num=new int[100];
    for(int i=0;i<k;i++){

        num[i]=input.nextInt();
    }
    s.sort(num);
    while(input.hasNext()){
        if(input.nextInt()>num[k-1]){
            if(input.nextInt()>num[k-2]){
                num[k-1]=num[k-2];
            }
            else{
                num[k-1]=input.nextInt();
            }
        }
    }
    System.out.println(num[k-1]);
}

}
不知道为什么不对,求助。。

2个回答

caozhy
caozhy   Ds   Rxr 2016.02.09 07:26

排序没有问题(当然内侧循环没必要对已经排序的部分再遍历了)。
int k=input.nextInt();
这里输入的k代表的应该是数组的大小,而不是第k大的k,建议将k重命名为n
while(input.hasNext()){
if(input.nextInt()>num[k-1]){
if(input.nextInt()>num[k-2]){
num[k-1]=num[k-2];
这里不对,你怎么又去读取输入呢?你这里需要输入的是你指定的k,然后直接返回或者输出num[n-k]

xuanjimingyue
xuanjimingyue 回复caozhy: 可是这个代码结果是错的,是为什么呢
2 年多之前 回复
caozhy
caozhy 回复xuanjimingyue: 这样也可以,相当于选择排序遍历前k次。
2 年多之前 回复
xuanjimingyue
xuanjimingyue 我的想法是,先将数组中前k个数进行递减排序,这样num[k-1]便是前k个数里的最小值,暂且将它作为所有数的数组中第k个最大值,然后比较后来输入的数是否比num[k-1]大,如果小于它则忽略,如果大于它就把数组中的一个元素挤出数组。如果是这样的想法,应该怎么修改代码呢?
2 年多之前 回复
91program
91program   Ds   Rxr 2016.02.08 17:07

首先排序的代码贴出来后不完整,其次排序算法的实现应该是有问题的:没有使用外层循环变量i。请使用搜索引擎,查找排序算法的实现。

91program
91program 回复xuanjimingyue: 建议你使用搜索引擎查找:Java 排序算法,我使用手机回答,不方便。
2 年多之前 回复
xuanjimingyue
xuanjimingyue 代码已重新编辑,都贴出来了,再帮忙看看呗
2 年多之前 回复
xuanjimingyue
xuanjimingyue 额外层循环不造怎么的没贴出来,sort方法是将数组递减排序,贴出来好像有点问题。
2 年多之前 回复
Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
Java源码-N个数字中第k个最大值的求解方法
翻开《数据结构》正文第一页,作者问了个问题:N个数字中的第k个最大值怎么计算? 作者认为,对于学编程两年的人而言,这个问题应该可以拿下。 事实上,这是我刚学习编程,考计算机等级考试3、4级时的基本问题,当时是在别人写好的C语言代码段里,加上一个嵌套的for循环,就轻松搞定。 然而,10多年后,我决定用已经学了这么久的Java来“徒手”写个小程序,解决这个问题。 经验: 1
不排序,两种方法找到无序数组的最大K个数
虽然不排序,这这两种方法都源于经典的排序算法的扩展   方式一,快速排序的扩展 /************************************************************************/ /*找到无序数组中最大的k个数 */ /**********************************************************
1、一组N个数,确定其中第k个最大值
一组N个数,确定其中第k个最大值《数据结构与算法分析(C语言描述)》一书已购多日,没有时间看,今天重拾,发现确是一本不可多得的好书,从第一章开始看起,决定将书中的每个问题均码一遍,为了兼顾Python和Java的学习,本博客采用三种编程语言同时编写,直到笔者对Python和Java已经很熟练为止。在本书的第1章引论的1.1节中(P1),作者给出了这样的一个问题: 设有一组N个数而要确定其中第k个最
(java)求两个排序数组(升序)中第K小的数
如题:求两个排好序的数组的第K个小的数 思路一:归并两个有序数组,按照顺序合并,最后找到第K-1位置的数。时间复杂度为O(N) 思路二:在技术博客上看到更好的思路,时间复杂度是OLog(m+n); 第k小的数字为x,那么数组1一定有i个数字小于x,数组2一定有j个数字小于x,注意i+j=k-1。因为k已知,所以我们只要搜索i即可。然后我们可以想象到,如果元素array1[i+1]为两个数组的
求数组中最小的k个数以及海量数据最大堆、multiset解决方案
【题目】 输入n个整数,找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字,则最小的4个数字是1,2,3,4,。 【方案一】 主要有两种方案。第一是利用我们熟知的 partition 算法,它是快速排序的核心,相信每个人都会。它可以用来求取数组的任意第 k 大的数,时间复杂度是O(n)。我们不断对数据 partition,当它返回的 index 为第 k-1
找出N个元素的数组中最大的K个数
题目: 给出 N 个整数(N可能很大,以致无法装入内存),找出前 K 个最大的整数 【解法一】 如果 N 的数量不是很大,例如在几千个左右,则在这种情况下,那我们就先排序一下,这里快速排序或者推排序都是很好的解决方案,平均时间复杂度为 O(N * log2N)。然后取出前 K 个,O(K)。 总共时间复杂度 O(N * log2N)+ O(K) = O(N * log2N)。 当 K =
求一个数组的最大k个数(java)
问题描述:求一个数组的最大k个数,如,{1,5,8,9,11,2,3}的最大三个数应该是,8,9,11 问题分析:     1.解法一:最直观的做法是将数组从大到小排序,然后选出其中最大的K个数,但是这样的解法,复杂度是O(logn*n),但是有时候并不需要排序,用简单的选择排序,或者是冒泡排序,那么就K轮的交换或者是选择,就可以得出结论,复杂度是O(n*k),当K很大的时候排序可能是更好的解
用堆排序寻找数组中最大的K个数
/*********************************************************************************** 堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法。 堆积是一个近似完全二叉树的结构,并同时满足堆积的性质: 即子结点的键值或索引总是小于(或者大于)它的父节点。 通常堆是通过一维数组来实现的。在起始数组为 0
选择问题——选出第K个最大的元素
最近在读《数据结构与算法分析(C语言描述)》,在优先队列(堆)一节中,作者总结了关于“选择问题——求第k个最大的元素”的几种思路,在此简单总结一下:第一种将这NN个数读进一个数组中,再通过某种简单的算法,比如冒泡排序、选择排序等,以递减顺序将数组进行排序,然后返回位置kk上的元素。假设使用最简单的排序算法,则运行时间为O(N2)O(N^2)第二种这是对第一种算法的简单优化。申请一个大小为kk的数组,
【leetcode】——从两个有序数组中寻找他们并集的第k小元素
题目题目:There are two sorted arrays A and B of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log(m + n)).两个排好序的数组A,B,大小分别为m,n,找到两个数组中所有元素