Question

我有两条幻灯:

for (int i = 0; i < n; i++) {
    while (arr[i] > 0 && arr[i] <= n && i!=arr[i]-1) {
        swap(arr[i], arr[arr[i] - 1]);
    }
}

而且:

for (int i = 0; i < n; i++) {
    while (arr[i] > 0 && arr[i] <= n && arr[i]!=arr[arr[i]-1)] {
        swap(arr[i], arr[arr[i] - 1]);
    }       
}

The difference between the two snippets is in while conditions where in the first we have i!=arr[i]-1 and in 2nd we have arr[i]!=arr[arr[i]-1). The first one runs me into time exceeded issue while the 2nd one runs without any issue.

我正在解决一个编码问题,如果我使用上文提到的首批注射器,我会遇到时间过长的问题,而第2次则不会遇到同样的问题。其余法典对两种氮都相同。我混淆了两种条件,即计算上的差别为何。

制约因素:

1 <= n <= 106
-10^6 <= arr[i] <= 10^6

Answer 1

Logically, if statement A: arr[i] != arr[arr[i]-1] holds, then statement B: i != arr[i]-1 holds.

换言之,符合A>/em>的一组投入的任何内容(见S_B)必须载于符合B>>/em>的一套投入中。因此,S_A是S_B的一个子集。考虑到贵投入空间并不小:1 <=n <= 10^6/code>,且投入可能有很大差异:-10^6 <= arr[i] <= 10^6,S_A > 或许是S_B>/em>的适当子集,而且很可能包含比S_B小得多的内容。


Hence, the number of calls to swap() for S_A is likely to be significantly less than that needed for S_B.

友情链接