Рубрики

ВОРОТА | GATE-CS-2006 | Вопрос 54

Для двух массивов чисел a 1 , a 2 , a 3 ,… a n и b 1 , b 2 , .. b n, где каждое число равно 0 или 1, самый быстрый алгоритм поиска наибольшего пролета (i, j) такой что a i + a i + 1 ,… .a j = b i + b i + 1 , .. b j . или сообщить, что нет такого промежутка,
(A) Занимает O (n 3 ) и Ω (2 n ) времени, если разрешено хеширование
(B) Принимает O (n 3 ) и Ω (n 2.5 ) время в ключевой модели сравнения
(C) Занимает θ (n) время и пространство
(D) Занимает O (√n) времени, только если сумма 2n элементов является четным числом

Ответ: (с)
Пояснение: Задача может быть решена за время θ (n) пространства и времени.

Идея основана на следующих наблюдениях.

  1. Поскольку существует всего n элементов, максимальная сумма равна n для обоих массивов.
  2. Разница между двумя суммами варьируется от -n до n . Таким образом, есть всего 2n + 1 возможных значений разницы.
  3. Если различия между суммами префиксов двух массивов становятся одинаковыми в двух точках, то подмассивы между этими двумя точками имеют одинаковую сумму.

Ниже приведен полный алгоритм.

  1. Создайте вспомогательный массив размером 2n + 1 для хранения начальных точек всех возможных значений различий (обратите внимание, что возможные значения различий варьируются от -n до n, т. Е. Имеется всего 2n + 1 возможных значений)
  2. Инициализируйте начальные точки всех различий как -1.
  3. Инициализируйте maxLen как 0 и префиксные суммы обоих массивов как 0, preSum1 = 0, preSum2 = 0
  4. Обходит оба массива от i = 0 до n-1.
    1. Обновить префиксные суммы: preSum1 + = arr1 [i], preSum2 + = arr2 [i]
    2. Вычислить разницу текущих сумм префиксов: curr_diff = preSum1 — preSum2
    3. Найти индекс в массиве diff: diffIndex = n + curr_diff // curr_diff может быть отрицательным и может идти до -n
    4. Если curr_diff равен 0, то i + 1 до сих пор maxLen
    5. Иначе, если curr_diff виден впервые, т. Е. Начальная точка текущей разности равна -1, то обновите начальную точку как i
    6. В противном случае (curr_diff НЕ виден в первый раз), затем рассмотрите i как конечную точку и найдите длину текущего диапазона той же суммы. Если эта длина больше, обновите maxLen
  5. Возврат maxLen

См. Longest Span с одинаковой суммой в двух двоичных массивах для полного выполнения кода
Тест на этот вопрос

Рекомендуемые посты:

ВОРОТА | GATE-CS-2006 | Вопрос 54

0.00 (0%) 0 votes