java - 优化代码以在 java 上传递 TLE 的建议
问题描述
我编写了一个代码,该代码将两个整数数组作为输入,并创建两个具有频率(整数出现次数)的树形图,并写入两个都不存在或频率不同的值,当数组大小时测试用例失败由于 TLE(超出时间限制),为 10^6。
import java.util.*;
//import java.util.stream.Collectors;
public class Solution {
public static void main(String args[])
{
Scanner s = new Scanner(System.in);
int x=s.nextInt();
int[] arr=new int[x];
int i,j,count=0;
for(i=0;i<x;i++)
{
arr[i]=s.nextInt();
}
Map<Integer, Integer> check=new TreeMap<Integer, Integer>();
for(i=0;i<x;i++)
{
for(j=0;j<x;j++)
{
if(arr[i]==arr[j])
{
count++;
}
}
check.put(arr[i], count);
count=0;
}
int y=s.nextInt();
int[] brr=new int[y];
for(i=0;i<y;i++)
{
brr[i]=s.nextInt();
}
Map<Integer, Integer> check1=new TreeMap<Integer, Integer>();
int count1=0;
for(i=0;i<y;i++)
{
for(j=0;j<y;j++)
{
if(brr[i]==brr[j])
{
count1++;
}
}
check1.put(brr[i], count1);
count1=0;
}
//System.out.println(check);
//System.out.println(check1);
ArrayList<Integer> store=new ArrayList<Integer>();
for(int key:check1.keySet())
{
if(check.containsKey(key))
{
int valb=check.get(key);
int vala=check1.get(key);
if(vala-valb!=0)
{
store.add(key);
}
}
else
{
store.add(key);
}
}
//Collections.sort(store);
for(i=0;i<store.size();i++)
{
System.out.print(store.get(i)+" ");
}
}
}
解决方案
而不是在嵌套循环中遍历相同的数组(O(n ^ 2)时间)计算这样的重复
for(i=0;i<x;i++)
{
for(j=0;j<x;j++)
{
if(arr[i]==arr[j])
{
count++;
}
}
check.put(arr[i], count);
count=0;
}
您可以为数组中的每个数字增加地图值。像这样的东西:
for (int item: arr) {
if (check.containsKey(item)) {
check.put(item, check.get(item) + 1);
} else {
check.put(item, 1);
}
}
最后,这会生成映射,其中每个键都是数组中的一个数字,键的每个值都是该数字在数组中出现次数的计数器。例如对于数组
[1, 2, 3, 4, 2, 3, 4, 5]
地图看起来像
{1 -> 1, 2 -> 2, 3 -> 2, 4 -> 2, 5 -> 1}
如果您使用 HashMap 而不是 TreeMap,这也会在 O(n) 时间内运行。
要对输出进行排序,您可以使用 TreeSet 而不是 ArrayList。
推荐阅读
- html - 为什么将包装 div 设置为 display: flex 会导致子元素表现得像内联元素?
- php - PHP:用增量整数替换键
- c# - 循环播放的音频文件结束了吗?
- go - protoc-gen-go 不在 linux 机器上执行
- data-structures - 为什么单链表的head_node(first_node)初始化时动态分配释放“两次”?
- javascript - 如何查看 Vue / Nuxt.js 中的浏览历史记录?
- sql - 聚合行以获得没有子集的唯一数组
- mongodb - 有没有办法在 mongo 的聚合函数中更新文档?
- expo - 将 wsl1 切换到 wsl2 后,expo 不会启动
- c - Program C, mv: cannot stat No such file or directory