Вопрос по algorithm – Проверьте, является ли массив B перестановкой A

10

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

Нам даны два несортированных целочисленных массива A и B. Мы должны проверить, является ли массив B перестановкой A. Как это можно сделать.? Даже XOR для чисел не будет работать, поскольку может быть несколько контрпримеров, которые имеют одинаковое значение XOR bt, не являющиеся перестановкой друг друга.

Решение должно быть O (n) времени и с пробелом O (1)

Любая помощь приветствуется! Благодарю.

Вам разрешено сортировать их? wildplasser
нет, это невозможно. Karoly Horvath
Если целые числа могут иметь произвольную точность, тогда 'n' в 'O (n)'; должен включать размер кодировки всех целых чисел и не может представлять количество элементов в массиве как таковое. Antti Huima
Следует отметить, что если целые числа имеют произвольную точность, такие вещи, как умножение, внезапно перестают работать как операции O (1), так как они имеют тенденцию работать для практических целей анализа алгоритма на целых числах размера регистра. Умножение двух O (n) больших чисел, скажем, не является операцией O (n). Бьюсь об заклад, вопрос был не о «целых числах произвольной точности», а о неуказанной (но ограниченной) точности. Во всяком случае, может быть, эта часть вопроса должна быть перепроверена. Antti Huima
Есть ли верхняя граница максимально допустимого целого числа? Или они могут быть целыми числами произвольной точности? templatetypedef

Ваш Ответ

9   ответов
1

вычислительный O (n), где n означает общую длину как A, так и B, и память O (1).

Если две серии A, B являются перестановками друг друга, то существует также серия C, являющаяся результатом перестановки A или B. Таким образом, проблема состоит в том, чтобы переставить A и B в серии C_A и C_B и сравнить их.

Одной из таких перестановок будет сортировка. Есть несколько алгоритмов сортировки, которые работают на месте, поэтому вы можете сортировать A и B на месте. Теперь в лучшем случае Smooth Sort сортирует с O (n) вычислительной и O (1) сложностью памяти, в худшем случае с O (n log n) / O (1).

Сравнение по элементам тогда происходит в O (n), но, поскольку в нотации O O (2 * n) = O (n), использование гладкой сортировки и сравнения даст вам проверку O (n) / O (1), если две серии являются перестановками друг друга. Однако в худшем случае это будет O (n log n) / O (1)

11

но вы можете сделать это за O (n) время и o (1) пространство. Выделить массив из 232 счетчики и установить их все на ноль. Это шаг O (1), потому что массив имеет постоянный размер. Затем переберите два массива. Для массива A увеличьте счетчики, соответствующие прочитанным целым числам. Для массива B уменьшите их. Если вы встретите отрицательное значение счетчика во время итерации массива B, остановите --- массивы не являются перестановками друг друга. В противном случае в конце (при условии, что A и B имеют одинаковый размер, что является обязательным условием), массив счетчиков равен нулю, а два массива являются перестановками друг друга.

Это O (1) пространство и O (n) время решения. Однако это не практично, но легко может стать решением вопроса об интервью. По крайней мере, так должно быть.

More obscure solutions

Using a nondeterministic model of computation, checking that the two arrays are not permutations of each others can be done in O(1) space, O(n) time by guessing an element that has differing count on the two arrays, and then counting the instances of that element on both of the arrays.

In randomized model of computation, construct a random commutative hash function and calculate the hash values for the two arrays. If the hash values differ, the arrays are not permutations of each others. Otherwise they might be. Repeat many times to bring the probability of error below desired threshold. Also on O(1) space O(n) time approach, but randomized.

In parallel computation model, let 'n' be the size of the input array. Allocate 'n' threads. Every thread i = 1 .. n reads the ith number from the first array; let that be x. Then the same thread counts the number of occurrences of x in the first array, and then check for the same count on the second array. Every single thread uses O(1) space and O(n) time.

Interpret an integer array [ a1, ..., an ] as polynomial xa1 + xa2 + ... + xan where x is a free variable and the check numerically for the equivalence of the two polynomials obtained. Use floating point arithmetics for O(1) space and O(n) time operation. Not an exact method because of rounding errors and because numerical checking for equivalence is probabilistic. Alternatively, interpret the polynomial over integers modulo a prime number, and perform the same probabilistic check.

Error: User Rate Limit Exceeded
Error: User Rate Limit Exceeded
Error: User Rate Limit Exceeded
Error: User Rate Limit Exceeded
Error: User Rate Limit Exceeded
0

Это не будет точно O (N), но это будет близко, в непатологических случаях.

Просто используйте [число% N] в качестве желаемого индекса или в цепочке, которая начинается там. Если какой-либо элемент должен быть заменен, он может быть помещен в индекс, где начался нарушающий элемент. Ополосните, вымойте, повторите.

ОБНОВИТЬ: Это похожая (N = M) хеш-таблица Он использовал цепочку, но мог быть понижен до открытой адресации.

Error: User Rate Limit Exceeded
Error: User Rate Limit Exceeded
Error: User Rate Limit Exceeded
Error: User Rate Limit Exceeded
Error: User Rate Limit Exceeded
1

Это исключает сортировку, а требование к пространству O (1) является подсказкой о том, что вам, вероятно, следует создать хеш строк и сравнить их.

Если у вас есть доступ к списку простых чисел, используйте решение cheeken.

Note: If the interviewer says you don't have access to a prime number list. Then generate the prime numbers and store them. This is O(1) because the Alphabet length is a constant.

Иначе здесь моя альтернативная идея. Я буду определять алфавит как = {a, b, c, d, e} для простоты. Значения для букв определяются как:

a, b, c, d, e
1, 2, 4, 8, 16

note: if the interviewer says this is not allowed, then make a lookup table for the Alphabet, this takes O(1) space because the size of the Alphabet is a constant

Определите функцию, которая может найти различные буквы в строке.

// set bit value of char c in variable i and return result
distinct(char c, int i) : int

E.g. distinct('a', 0) returns 1
E.g. distinct('a', 1) returns 1
E.g. distinct('b', 1) returns 3

Таким образом, если вы перебираете строку «aab» отличная функция должна дать 3 в результате

Определите функцию, которая может вычислить сумму букв в строке.

// return sum of c and i
sum(char c, int i) : int

E.g. sum('a', 0) returns 1
E.g. sum('a', 1) returns 2
E.g. sum('b', 2) returns 4

Таким образом, если вы перебираете строку «aab» функция суммы должна дать 4 в результате

Определите функцию, которая может вычислять длину букв в строке.

// return length of string s
length(string s) : int

E.g. length("aab") returns 3

Запуск методов на двух строках и сравнение результатов занимает O (n) времени выполнения. Сохранение хеш-значений занимает O (1) в пространстве.

 e.g. 
 distinct of "aab" => 3
 distinct of "aba" => 3
 sum of "aab => 4
 sum of "aba => 4
 length of "aab => 3
 length of "aba => 3

Поскольку все значения равны для обеих строк, они должны быть перестановкой друг друга.

EDIT: Решения не верны с данными значениями алфавита, как указано в комментариях.

Error: User Rate Limit Exceeded
Error: User Rate Limit Exceeded
Error: User Rate Limit Exceeded
Error: User Rate Limit Exceededfunction hash(str){var arr = {'a':1, 'b':2, 'c':4, 'd':8, 'e':16}; return str.split('').reduce(function(a,b){ return a + arr[b]; }, 0); }
3

то может работать следующий подход:

Create a HashMap, Key as array element, Value as number of occurances. (To handle multiple occurrences of the same number) Traverse array A. Insert the array elements in the HashMap. Next, traverse array B. Search every element of B in the HashMap. If the corresponding value is 1, delete the entry. Else, decrement the value by 1. If we are able to process entire array B and the HashMap is empty at that time, Success. else Failure.

HashMap будет использовать постоянное пространство, и вы будете обходить каждый массив только один раз.

Не уверен, что это то, что вы ищете. Дайте мне знать, если я пропустил какое-либо ограничение относительно пространства / времени.

Error: User Rate Limit Exceeded
Error: User Rate Limit Exceeded
Error: User Rate Limit Exceeded
Error: User Rate Limit Exceeded
5

что опубликовал это как ответ, так как это действительно должен быть комментарий к ответу antti.huima, но у меня нет репутации, чтобы комментировать.

Размер массива счетчиков, по-видимому, равен O (log (n)), поскольку он зависит от количества экземпляров данного значения во входном массиве.

Например, пусть входной массив A будет всеми 1 с длиной (2 ^ 32) + 1. Это потребует счетчика размером 33 бита для кодирования (который на практике удвоил бы размер массива, но давайте останемся с теорией). Удвойте размер A (все еще все 1 значения), и вам нужно 65 бит для каждого счетчика, и так далее.

Это очень придирчивый аргумент, но эти вопросы интервью, как правило, очень придирчивы.

0

который имеет низкую вероятность ошибки.

Ключ должен использоватьуниверсальная хеш-функция.

def hash(array, hash_fn):
  cur = 0
  for item in array:
    cur ^= hash_item(item)
  return cur

def are_perm(a1, a2):
  hash_fn = pick_random_universal_hash_func()
  return hash_fn(a1, hash_fn) == hash_fn(a2, hash_fn) 

Если массивы являются перестановками, это всегда будет правильно. Если они отличаются, алгоритм может неправильно сказать, что они одинаковы, но это будет сделано с очень низкой вероятностью. Кроме того, вы можете получить экспоненциальное уменьшение вероятности ошибки при линейном объеме работы, задав много вопросов are_perm () для одного и того же ввода, если оно когда-либо скажет «нет», то они определенно не являются перестановками друг друга.

7

вы можете решить эту проблему, используя свойства простой факторизации.

Для обоих массивов вычислите произведение Prime [i] для каждого целого числа i, где Prime [i] - это i-е простое число. Значения произведений массивов равны, если они являются перестановками друг друга.

Первичная факторизация помогает здесь по двум причинам.

Multiplication is transitive, and so the ordering of the operands to calculate the product is irrelevant. (Some alluded to the fact that if the arrays were sorted, this problem would be trivial. By multiplying, we are implicitly sorting.) Prime numbers multiply losslessly. If we are given a number and told it is the product of only prime numbers, we can calculate exactly which prime numbers were fed into it and exactly how many.

Пример:

a = 1,1,3,4
b = 4,1,3,1
Product of ith primes in a = 2 * 2 * 5 * 7 = 140
Product of ith primes in b = 7 * 2 * 5 * 2 = 140

Тем не менее, мы, вероятно, не разрешили доступ к списку простых чисел, но в противном случае это кажется хорошим решением, поэтому я решил опубликовать его.

Error: User Rate Limit Exceeded
0

Я не могу доказать это, но я думаю, что это может быть правдой.

Поскольку все элементы массивовintegersпредположим, что каждый массив имеет 2 элемента, и у нас есть

a1 + a2 = s
a1 * a2 = m

b1 + b2 = s
b1 * b2 = m

then {a1, a2} == {b1, b2}

если это верно, это верно для массивов, имеющих n-элементы.

Таким образом, мы сравниваем сумму и произведение каждого массива, если они равны, один является перестановкой другого.

Error: User Rate Limit Exceeded
Error: User Rate Limit Exceeded

Похожие вопросы