Самый быстрый алгоритм для нахождения наибольшего интервала (i,j) такого, что ai + ai+1 ++aj = bi + bi+1 ++bj в массивах a и b

Я столкнулся с этой проблемой при подготовке к экзаменам.

Учитывая два массива чисел a1,..., an и b1,....,bn, где каждое число равно 0 или 1, самый быстрый алгоритм для нахождения наибольшего интервала (i,j), такой что , ai + ai+1 +....+aj = bi + bi+1 +....+bj или сообщить, что такого диапазона нет.

(A) Занимает O(3^n) и омега(2^n) время, если разрешено хеширование.

(B) Занимает O(n^3) и омега(n^2,5) и время в режиме сравнения ключей

(C) Занимает тета(n) время и пространство

(D) Занимает O (квадратный корень (n)) времени, только если сумма 2n элементов является четным числом.


arrays array-algorithms asymptotic-complexity
person Community    schedule 03.11.2011    source источник

Ответы (2)


arrow_upward
1
arrow_downward

Единственное решение, которое я могу придумать, имеет время O (n ^ 2) и omega (n), если кто-то потрудится сделать правильную проверку. Вероятно, его можно было бы улучшить, если бы кому-нибудь удалось найти способ воспользоваться преимуществами всех значений, равных 0 и 1.

int[] a = { 1, 1, 0, 1, 1, 0, 1, 0, 1 };
int[] b = { 0, 1, 0, 0, 1, 1, 0, 1, 0 };

int lastSum = 0; int lastI = 0; int lastJ = 0;
int sumA = 0; int sumB = 0; 
for(int i = 0; i < a.Length; i++) // start the sum at [i].
{
    sumA = a[i]; sumB = b[i];
    for (int j = i + 1; j < a.Length; j++) // summing ends on [j]
    //do
    {
        if (sumA == sumB && (lastJ - lastI < j - i))
        {
            lastSum = sumA;
            lastI = i; lastJ = j;
            if (j == a.Length - 1) // you will never find a bigger interval.
            {
                Console.Out.WriteLine("(i, j) = (" + lastI + ", " + lastJ + ")");
                return;
            }
        }
        sumA += a[j];
        sumB += b[j];
    }
}
Console.Out.WriteLine("(i, j) = (" + lastI + ", " + lastJ + ")");
person Liz    schedule 03.11.2011

arrow_upward
2
arrow_downward

Вот алгоритм O (n),

l=[1,1,1,1,0,1,0,1,1,0,1,0,0,0,1,1,1,1,0]
m=[0,0,0,0,1,0,1,1,1,0,0,0,1,1,1,0,0,0,1]
delta=[]
for i in range(0,len(l)):
    delta.append(l[i]-m[i])

leftsum=[0]
for i in range(1,len(l)+1):
    leftsum.append(leftsum[i-1]+delta[i-1])

sumHash=[-1]*len(l)

maxLen=0;
leftIndex=-1
rightIndex=-1

for i in range(0,len(l)+1):
    if sumHash[leftsum[i]]!=-1:
        if maxLen<i-sumHash[leftsum[i]]:
            maxLen=i-sumHash[leftsum[i]]
            leftIndex=sumHash[leftsum[i]]
            rightIndex=i-1
    else:
        sumHash[leftsum[i]]=i

print 'len=',maxLen,'left=',leftIndex,'right=',rightIndex
person Nikhil George    schedule 31.01.2013