为什么这段代码会导致超时错误？
为什么这段代码会导致超时错误？
提问于 2020-07-19 09:56:24
我在解决这问题。
给定两个排序数组，arr1[]和arr2[]按非递减顺序，大小为n和m，任务是将两个排序数组合并为一个排序数组(按非递减顺序)。
注意:预期的时间复杂度是O((n+m) log(n+m))。不要使用额外的空间。
以下代码的时间复杂度为O(n log )。尽管如此，它还是给了我一个超时错误。
我哪里出问题了？
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);
}
}
}回答 1
Stack Overflow用户
回答已采纳
发布于 2020-07-19 13:07:14
这个网站有一些问题。多次提交相同的解决方案。
超时是由于涉及了大量的读写操作。
您使用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);
}
}
}Geeks的判决是接受的，用于上面的代码：
PS:尝试多次提交相同的解决方案。你将得到正确的答案作为裁决。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/62978753
复制相关文章
相似问题
腾讯云开发者
