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

huangapple go评论58阅读模式
英文:

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

问题

我在LeetCode的双周竞赛中解决了一个问题。

链接:https://leetcode.com/problems/find-servers-that-handled-most-number-of-requests/

起初我尝试了一种暴力方法,但我对它能否奏效持怀疑态度。事实证明,我最终遇到了超时错误。后来,在使用TreeSet和PQs解决了这个问题后,我发现了一个几乎与我自己的暴力尝试完全相同的提交。而且这个解法被接受了。我无法找到任何区别。有人能指出其中的区别吗?

我的代码:

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]++;
                time[x] = arrival[i] + load[i]; 
                break;
            }
        }
    }
    List<Integer> ans = new ArrayList<Integer>();
    int max = Integer.MIN_VALUE;
    for (int i = 0; i < count.length; i++) {
        if (count[i] == max)
            ans.add(i);
        else if (count[i] > max) {
            ans = new ArrayList<Integer>();
            ans.add(i);
            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++) {
        if (cnt[i] == max) res.add(i);
        else if (cnt[i] > max) {
            max = cnt[i];
            res = new ArrayList<>();
            res.add(i);
        }
    }
    return res;
}
英文:

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

Link: https://leetcode.com/problems/find-servers-that-handled-most-number-of-requests/

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]++;
                    time[x] = arrival[i] + load[i]; 
                    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)
                ans.add(i);
            else if (count[i] &gt; max) {
                ans = new ArrayList&lt;Integer&gt;();
                ans.add(i);
                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++) { if (cnt[i] == max) res.add(i); else if (cnt[i] &gt; max) { max = cnt[i]; res = new ArrayList&lt;&gt;(); res.add(i); } } return res; }

答案1

得分: 0

我唯一(勉强)能看出来的有意义的区别是,在你的 j 循环内部每次访问 arrival[i]load[i],而被接受的解决方案将它们放在循环外的变量中,并每次引用这些变量,这意味着他们的内部循环(显然)稍微更快。难以置信的是,在这个特定的 LeetCode 问题中,这似乎决定了“已接受”和“超出时间限制”之间的区别。

具体来说,我在你的代码中将这个循环进行了重写:

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

重写为了与你发布的第二个被接受的解决方案相匹配:

int currentArrival = arrival[i];
int currentLoad = load[i];
for (int j = 0; j &lt; k; j++, x++) {
    if (x == k) x = 0;
    if (time[x] &lt;= currentArrival) {
        count[x]++;
        time[x] = currentArrival + currentLoad;
        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]++;
        time[x] = arrival[i] + load[i];
        break;
    }
}

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

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

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

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定