13

这是编程难题。我们有两个数组 A 和 B。它们都只包含 0 和 1。

我们必须有两个索引i, j，这样

 a[i] + a[i+1] + .... a[j] = b[i] + b[i+1] + ... b[j].

我们还必须最大化 i 和 j 之间的差异。寻找 O(n) 解决方案。

我找到O(n^2)了解决方案，但没有得到O(n).

4

4 回答 4

6

最佳解决方案是O(n)

首先 let c[i] = a[i] - b[i]，然后问题变成 find i、j、 whichsum(c[i], c[i+1], ..., c[j]) = 0和 max j - i。

其次让d[0] = 0, d[i + 1] = d[i] + c[i], i >= 0, 然后问题变成 find i , j , whichd[j + 1] == d[i]和 max j - i。

的值d在范围内[-n, n]，所以我们可以使用下面的代码来找到答案

answer = 0, answer_i = 0, answer_j = 0
sumHash[2n + 1] set to -1
for (x <- 0 to n) {
  if (sumHash[d[x]] == -1) {
    sumHash[d[x]] = x
  } else {
    y = sumHash[d[x]]
    // find one answer (y, x), compare to current best
    if (x - y > answer) {
      answer = x - y
      answer_i = y
      answer_j = y
    }
  }
}
于 2012-10-31T09:23:58.130 回答
4

这是一个O(n)解决方案。

我使用的事实是sum[i..j] = sum[j] - sum[i - 1].

我保留每个找到的总和的最左边的位置。

    int convertToPositiveIndex(int index) {
        return index + N;
    } 

    int mostLeft[2 * N + 1];
    memset(mostLeft, -1, sizeof(mostLeft));

    int bestLen = 0, bestStart = -1, bestEnd = -1;

    int sumA = 0, sumB = 0;
    for (int i = 0; i < N; i++) {
        sumA += A[i];
        sumB += B[i];

        int diff = sumA - sumB;
        int diffIndex = convertToPositiveIndex(diff);

        if (mostLeft[diffIndex] != -1) {
            //we have found the sequence mostLeft[diffIndex] + 1 ... i
            //now just compare it with the best one found so far 
            int currentLen = i - mostLeft[diffIndex];
            if (currentLen > bestLen) {
                bestLen = currentLen;
                bestStart = mostLeft[diffIndex] + 1;
                bestEnd = i;
            }
        }

        if (mostLeft[diffIndex] == -1) {
            mostLeft[diffIndex] = i;
        }
    }

cout << bestStart << " " << bestEnd << " " << bestLen << endl;

PSmostLeft数组是2 * N + 1，因为有底片。

于 2012-10-31T09:18:19.853 回答
4

基本上，我的解决方案是这样的。

从一开始就采取一个变量来处理差异。

int current = 0;
for index from 0 to length
    if a[i] == 0 && b[i] == 1
        current--;
    else if a[i] == 1 && b[i] == 0
        current++;
    else
        // nothing;

找到变量具有相同值的位置，表示其间有相等的 1 和 0。

伪代码：

这是我的主要解决方案：

int length = min (a.length, b.length);
int start[] = {-1 ... -1}; // from -length to length
start[0] = -1;
int count[] = {0 ... 0};   // from -length to length
int current = 0;
for (int i = 0; i < length; i++) {
    if (a[i] == 0 && b[i] == 1)
        current--;
    else if (a[i] == 1 && b[i] == 0)
        current++;
    else
        ; // nothing

    if (start[current] == -1) // index can go negative here, take care
        start[current] = current;
    else
        count[current] = i - start[current];
}
return max_in(count[]);
于 2012-10-31T09:21:45.347 回答
4

这是一个相当简单的 O(N) 解决方案：

让sa = [s1, s2, s3.. sn]在哪里si = sum(a[0:i])和类似的sb

然后sum(a[i:j]) = sa[j]-sa[i] 和sum(b[i:j]) = sb[j] - sb[i]

请注意，因为总和每次只增加 1，我们知道0 <= sb[N], sa[N] <=N

difference_array = [d1, d2, .. dn]在哪里di = sb[i] - sa[i] <= N

注意 if di = dj， thensb[i] - sa[i] = sb[j] - sa[j]这意味着它们具有相同的总和（sum(b[i:j]) and sum(a[i:j])从上面重新排列）。

现在对于每个差异，我们需要它的最大位置出现和最小位置出现

现在对于每个差值di，max - min 之间的差值是等和的ij 部分。找到最大的最大最小值，你就完成了。

应该工作的示例代码：

a = []
b = []
sa = [0]
sb = [0]
for i in a:
    sa.append(sa[-1] + i)
for i in b:
    sb.append(sb[-1] + i)

diff = [sai-sbi for sai, sbi in zip(sa, sb)]
min_diff_pos = {}
max_diff_pos = {}
for pos, d in enumerate(diff):
    if d in min_diff_pos:
        max_diff_pos[d] = pos
    else:
        min_diff_pos[d] = pos

ans = min(max_diff_pos[d] - min_diff_pos[d] for d in diff)
于 2012-10-31T09:22:10.110 回答