还能怎么优化,4 5TLE

P1923 【深基9.例4】求第 k 小的数

Mr_xiao @ 2022-11-20 20:15:01

import java.util.Scanner;

public class Main {

    public static void main(String[] args)  {

        Scanner scanner=new Scanner(System.in);
        int num[]=new int[2];
        for (int i = 0; i < num.length; i++) {
            num[i]=scanner.nextInt();
        }
        int nums[]=new int[num[0]];
        int temp[]=new int[num[0]];
        for (int i = 0; i < num[0]; i++) {
            nums[i]=scanner.nextInt();
        }

        scanner.close();

        mergeSort(nums, 0, nums.length - 1, temp);

        System.out.println(nums[num[1]]);
    }

    public static void mergeSort(int arr[], int left, int right, int temp[]) {
        if (left < right) {
            int mid = (right - left) / 2 + left;

            mergeSort(arr, left, mid, temp);

            mergeSort(arr, mid+1, right, temp);

            merge(arr, left, right, mid, temp);
        }

    }

    public static void merge(int arr[], int left, int right, int mid, int temp[]) {
        int counter = 0;
        int l = left;
        int r = mid + 1;

        while (l <= mid && r <= right) {

            if (arr[l] <= arr[r]) {
                temp[counter] = arr[l];
                l++;
                counter++;
            } else {
                temp[counter] = arr[r];
                r++;
                counter++;
            }

        }

        if (l <= mid) {
            int num = l;
            for (int i = num; i <= mid; i++) {
                temp[counter] = arr[l];
                l++;
                counter++;
            }

        }

        if (r <= right) {
            int num = r;
            for (int i = num; i <= right; i++) {
                temp[counter] = arr[r];
                r++;
                counter++;
            }

        }

        counter = 0;

        int templeft = left;
        while (templeft <= right) {
            arr[templeft] = temp[counter];
            counter++;
            templeft++;
        }

    }

}

|