算法---区间K大数查找 Java 蓝桥杯ALGO-1

 import java.util.Arrays;

 import java.util.Scanner;

 public class Main {

     public static void main(String[] args) {

     Scanner aScanner = new Scanner(System.in);

     int n= aScanner.nextInt();   //读第一个

     long a[] = new long[n];      //存放数组

     long b[] = new long[n];      //备用数组

     for(int i=0;i<n;i++)

     {

         a[i] = aScanner.nextInt();

     }

     int m = aScanner.nextInt();

     int []l = new int[1001];

     int []r = new int[1001];

     int []k = new int[1001];

     for(int i=0;i<m;i++)

     {

         l[i] = aScanner.nextInt();

         r[i] = aScanner.nextInt();

         k[i] = aScanner.nextInt();

         for(int j=l[i]-1;j<r[i];j++)

         {

             b[j-l[i]+1] = a[j];

         }

         Arrays.sort(b);

         System.out.println(b[b.length-k[i]]);

         Arrays.fill(b, '\0');

     }

     }

 }

　　刚开始做的时候使用的二维数组，使用冒泡排序，但涉及到了三层循环，最后虽然结果出来了，但是运行超时。

　　于是就需求更优化的方法，后来参考网上的标准答案后有一个排序函数可以用sort()函数,直接使用Arrays.sort()函数对数组进行从小到大的排序，每次得出结果后直接输出。

同时循环一次后需要对结果进行清空，我使用的是Arrays.fill()函数，用‘\0’来填充，但也有不足的地方，会在清空后都是0的形式存在，数组的长度没有变化，所以需要我之后进一步改进，最后的评测结果如图：仍旧有一个运行超时！！，仅供参考

注：网络查找标准答案代码（Java，未加头文件，自行加入）：

public class Main

{

    private static BufferedInputStream in = new BufferedInputStream(System.in);

    public static void main(String[] args) throws IOException {

        int []nums = new int[readint()];

        for(int i=0;i<nums.length;i++)

        {

            nums[i] = readint();

        }

        for(int i=readint();i>0;i--)

        {

            int a = readint();

            int b = readint();

            int c = readint();

            int[] tn = new int[b-a+1];

            for(int j=0;j<tn.length;j++)

            {

                tn[j] = nums[a-1+j];

            }

            Arrays.sort(tn);

            System.out.println(tn[tn.length-c]);

        }

    }

    private static int readint()throws IOException {

        // TODO Auto-generated method stub

        int i,sum=0;

        while(((i=in.read())&48)!=48||i>57); 

        for(;(i&56)==48||(i&62)==56;i=in.read())

            sum = sum*10+(i&15);

        return sum;

    }

}

巴特西

算法---区间K大数查找 Java 蓝桥杯ALGO-1

最新文章

热门文章