为什么此代码会给我超时错误？

Question

我正在解决 this 问题。

给定两个按非降序排序的数组 arr1[] 和 arr2[]，大小为 n 和 m。任务是将两个排好序的数组合并为一个排好序的数组（非降序排列）。

注：预计时间复杂度为O((n+m) log(n+m))。不要使用额外的 space.
以下代码的时间复杂度为 O(n log m)。仍然，它给我一个超时错误。

我哪里错了？



import java.util.*;
import java.lang.*;
import java.io.*;

class GFG {
    public static void main (String[] args) throws IOException {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
        
        while(t-- > 0){
            StringTokenizer st = new StringTokenizer(br.readLine());
            int len1 = Integer.parseInt(st.nextToken());
            int len2 = Integer.parseInt(st.nextToken());
            int[] nums1 = new int[len1];
            int[] nums2 = new int[len2];
            
             st = new StringTokenizer(br.readLine());
            
            for(int i = 0; i<len1; i++)
                nums1[i] = Integer.parseInt(st.nextToken());
                
             st = new StringTokenizer(br.readLine());
            
            for(int i = 0; i<len2; i++)
                nums2[i] = Integer.parseInt(st.nextToken());
                
            int temp;
            for(int i =0; i<len1; i++){
                if (nums1[i] > nums2[0]){
                     temp = nums1[i];
                     nums1[i] = nums2[0];
                     nums2[0] = temp;
                     Heapify(nums2,0,len2);
                }
                
            } 
            
            
            for(int i = 0; i<len1; i++)
                System.out.print(nums1[i]+" ");
                
            Arrays.sort(nums2);
            for(int i = 0; i<len2; i++)
                System.out.print(nums2[i]+" ");
            System.out.println();
            
            
        }
        
    }
    
    static void Heapify(int[] nums, int i, int len){
        
        int l = 2 * i+1;
        int r = 2 * i + 2;
        int smallest = i;
        
        if (l < len && nums[l] < nums[i] ){
            smallest = l;
        }
        if (r < len && nums[r] < nums[smallest] ){
            smallest = r;
        }
        if (smallest != i){
            int temp = nums[i];
            nums[i] = nums[smallest];
            nums[smallest] = temp;
            Heapify(nums,smallest,len);
        }
        
    }
    
}

Answer 1

网站有一些问题。多次提交相同的解决方案。

超时是因为涉及到大量的读写操作。

您使用 BufferedReader 针对读取操作优化了它。

我在以下实现中使用 BufferedWriter 针对 写入操作 对其进行了优化：

import java.util.*;
import java.lang.*;
import java.io.*;

class GFG {
    public static void main (String[] args) throws IOException {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
        
        while(t-- > 0){
            StringTokenizer st = new StringTokenizer(br.readLine());
            int len1 = Integer.parseInt(st.nextToken());
            int len2 = Integer.parseInt(st.nextToken());
            int[] nums1 = new int[len1];
            int[] nums2 = new int[len2];
            
             st = new StringTokenizer(br.readLine());
            
            for(int i = 0; i<len1; i++)
                nums1[i] = Integer.parseInt(st.nextToken());
                
             st = new StringTokenizer(br.readLine());
            
            for(int i = 0; i<len2; i++)
                nums2[i] = Integer.parseInt(st.nextToken());
                
            int temp;
            for(int i =0; i<len1; i++){
                if (nums1[i] > nums2[0]){
                     temp = nums1[i];
                     nums1[i] = nums2[0];
                     nums2[0] = temp;
                     Heapify(nums2,0,len2);
                }
                
            } 
            
            BufferedWriter log = new BufferedWriter(new OutputStreamWriter(System.out));
            
        
            
            
            for(int i = 0; i<len1; i++)
                log.write(nums1[i]+" ");
                
            Arrays.sort(nums2);
            for(int i = 0; i<len2; i++)
                log.write(nums2[i]+" ");
            log.write("\n");
            
            log.flush();    
            
        }
        
    }
    
    static void Heapify(int[] nums, int i, int len){
        
        int l = 2 * i+1;
        int r = 2 * i + 2;
        int smallest = i;
        
        if (l < len && nums[l] < nums[i] ){
            smallest = l;
        }
        if (r < len && nums[r] < nums[smallest] ){
            smallest = r;
        }
        if (smallest != i){
            int temp = nums[i];
            nums[i] = nums[smallest];
            nums[smallest] = temp;
            Heapify(nums,smallest,len);
        }
        
    }
    
}

对于上述代码，极客对极客的裁决是接受：

PS: 尝试多次提交相同的解决方案。您将得到正确答案作为判决。

为什么此代码会给我超时错误？

Why does this code gives me timeout error?

java

algorithm

heap

timeout

data-structures