# Two similar codes: one throws TLE while the other doesn't. Can't figure out the difference between both

go评论57阅读模式

Two similar codes: one throws TLE while the other doesn't. Can't figure out the difference between both

# 问题

``````public List<Integer> busiestServers(int k, int[] arrival, int[] load) {
int[] time = new int[k];
int[] count = new int[k];
for (int i = 0; i < arrival.length; i++) {
int x = i % k;
for (int j = 0; j < k; j++, x++) {
if (x == k) x = 0;
if (time[x] <= arrival[i]) {
count[x]++;
break;
}
}
}
List<Integer> ans = new ArrayList<Integer>();
int max = Integer.MIN_VALUE;
for (int i = 0; i < count.length; i++) {
if (count[i] == max)
else if (count[i] > max) {
ans = new ArrayList<Integer>();
max = count[i];
}
}
return ans;
}
``````

``````public List<Integer> busiestServers(int k, int[] as, int[] ls) {
int exp[] = new int[k], cnt[] = new int[k], max = 0;
for (int i = 0; i < as.length; i++) {
int t = as[i], l = ls[i], s = i % k;
for (int j = 0; j < k; j++, s++) {
if (s == k) s = 0;
if (exp[s] <= t) {  // 检查上一个任务的结束时间是否小于等于当前任务的到达时间；
cnt[s]++;
exp[s] = t + l;  // 加载任务并设置任务结束时间；
break;
}
}
}
List<Integer> res = new ArrayList<>();
for (int i = 0; i < k; i++) {
else if (cnt[i] > max) {
max = cnt[i];
res = new ArrayList<>();
}
}
return res;
}
``````

I was solving a problem during the biweekly contest on Leetcode.

I first tried a brute force but I was sceptical if it would work. And as it turned out, I ended up with a TLE. Later after having solved the question using TreeSet and PQs, I found one submission which was almost a replica of my own brute force attempt. And this one was accepted. I was unable to find any differences. Can anyone point them out to me?

MY CODE:

``````public List&lt;Integer&gt; busiestServers(int k, int[] arrival, int[] load) {
int[] time = new int[k];
int[] count = new int[k];
for (int i = 0; i &lt; arrival.length; i++) {
int x = i%k;
for (int j = 0; j &lt; k; j++, x++) {
if (x == k) x = 0;
if (time[x] &lt;= arrival[i]) {
count[x]++;
break;
}
}
}
List&lt;Integer&gt; ans = new ArrayList&lt;Integer&gt;();
int max = Integer.MIN_VALUE;
for (int i = 0; i &lt; count.length; i++) {
if (count[i] == max)
else if (count[i] &gt; max) {
ans = new ArrayList&lt;Integer&gt;();
max = count[i];
}
}
return ans;
}
``````

THE CODE THAT WAS ACCEPTED:

``````public List&lt;Integer&gt; busiestServers(int k, int[] as, int[] ls) {
int exp[] = new int[k], cnt[] = new int[k], max = 0;
for (int i = 0; i &lt; as.length; i++) {
int t = as[i], l = ls[i], s = i % k;
for (int j = 0; j &lt; k; j++, s++) {
if (s == k) s = 0;
if (exp展开收缩 &lt;= t) {  // check if free by last job expiration time;
cnt展开收缩++;
exp展开收缩 = t + l;  // load the job and set the job exp time;
break;
}
}
}
List&lt;Integer&gt; res = new ArrayList&lt;&gt;();
for (int i = 0; i &lt; k; i++) {
else if (cnt[i] &gt; max) {
max = cnt[i];
res = new ArrayList&lt;&gt;();
}
}
return res;
}
``````

# 答案1

``````for (int j = 0; j &lt; k; j++, x++) {
if (x == k) x = 0;
if (time[x] &lt;= arrival[i]) {
count[x]++;
break;
}
}
``````

``````int currentArrival = arrival[i];
for (int j = 0; j &lt; k; j++, x++) {
if (x == k) x = 0;
if (time[x] &lt;= currentArrival) {
count[x]++;
break;
}
}
``````

The only (barely) meaningful difference I can see is that you access `arrival[i]` and `load[i]` each time inside your `j` loop, whereas the accepted solution puts them in variables outside the loop and refers to those variables every time, which means their inner loop is (apparently) slightly faster. Incredibly, for this specific Leetcode problem, this does seem to make the difference between Accepted and Time Limit Exceeded.

Specifically, I rewrote this loop in your code:

``````for (int j = 0; j &lt; k; j++, x++) {
if (x == k) x = 0;
if (time[x] &lt;= arrival[i]) {
count[x]++;
break;
}
}
``````

as follows to match the second solution you posted, which was Accepted:

``````int currentArrival = arrival[i];
for (int j = 0; j &lt; k; j++, x++) {
if (x == k) x = 0;
if (time[x] &lt;= currentArrival) {
count[x]++;
break;
}
}
``````

• 本文由 发表于 2020年10月6日 15:25:13
• 转载请务必保留本文链接：https://go.coder-hub.com/64221110.html
• java

go 79

go 52

go 60

go 88