Ответ 1

Это, вероятно, самый быстрый способ сделать это в Java, используя предложение HotLick в комментариях. Он делает предположение, что b.length == a.length + 1, поэтому b - это больший массив с дополнительным "уникальным" элементом.

public static int getUniqueElement(int[] a, int[] b) {
    int ret = 0;
    int i;
    for (i = 0; i < a.length; i++) {
        ret = ret ^ a[i] ^ b[i];
    }
    return ret ^ b[i];
}

Даже если предположение не может быть сделано, вы можете легко расширить его, включив случай, когда либо a, либо b может быть большим массивом с уникальным элементом. Он все еще O (m + n), хотя и сокращаются только служебные данные цикла/назначения.

Изменить:

Из-за деталей реализации языка это все же (удивительно) самый быстрый способ сделать это в CPython.

def getUniqueElement1(A, B):
    ret = 0
    for a in A: ret = ret ^ a
    for b in B: ret = ret ^ b
    return ret

Я протестировал это с помощью модуля timeit и нашел интересные результаты. Оказывается, что longhand ret = ret ^ a действительно быстрее в Python, чем сокращенное ret ^= a. Итерация по элементам цикла происходит намного быстрее, чем повторение индексов, а затем выполнение подстрочных операций в Python. Вот почему этот код намного быстрее, чем мой предыдущий метод, когда я пытался скопировать Java.

Я предполагаю, что мораль этой истории заключается в том, что нет правильного ответа, потому что вопрос в любом случае является фиктивным. Как показывает OP в другом ответе ниже, выясняется, что вы не можете двигаться быстрее, чем O (m + n), и его учитель просто тянул ногу. Таким образом, проблема сводится к поиску самого быстрого способа перебора всех элементов в двух массивах и накопления XOR всех из них. И это означает, что он полностью зависит от реализации языка, и вам нужно провести некоторое тестирование и играть, чтобы получить истинное "самое быстрое" решение в любой реализации, которую вы используете, потому что общий алгоритм не изменится.

Ответ 2

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

Я должен начать с разъяснения того, что я имел в виду:

он намекнул, что есть еще более быстрый способ сделать это

Суть нашего разговора заключалась в следующем: он сказал, что мой подход XOR был интересен, и мы поговорили некоторое время о том, как я пришел к моему решению. Он спросил меня, думаю ли я, что мое решение было оптимальным. Я сказал, что сделал (по причинам, упомянутым в моем вопросе). Затем он спросил меня: "Ты уверен?" с видом на его лице я могу только описать как "самодовольный". Я колебался, но сказал, да. Он спросил меня, могу ли я придумать лучший способ сделать это. Я был очень похож: "Вы имеете в виду более быстрый способ?" но вместо того, чтобы дать мне прямой ответ, он сказал мне подумать об этом. Я сказал, что буду.

Поэтому я подумал об этом, конечно, что мой учитель знал то, чего я не знал. И после того, как я не придумал ничего за день, я пришел сюда.

То, что мой учитель действительно хотел, чтобы я делал, был защищать мое решение как оптимальное, а не пытаться найти лучшее решение. Как он выразился: создание приятного алгоритма - легкая часть, сложная часть доказывает, что она работает (и что она лучшая). Он подумал, что было довольно забавно, что я потратил так много времени на Find-A-Better-Way Land вместо разработки простого доказательства O (n), которое заняло бы значительно меньше времени (мы закончили это, см. Ниже, если вам интересно).

Итак, я думаю, большой урок узнал здесь. Я буду принимать ответ Shashank Gupta, потому что я думаю, что он действительно может ответить на исходный вопрос, хотя вопрос был ошибочным.

Я оставлю вас, ребята, с аккуратным маленьким однострочным Python, который я нашел, набрав доказательство. Это не более эффективно, но мне это нравится:

def getUniqueElement(a, b):
    return reduce(lambda x, y: x^y, a + b)

Очень неформальное "доказательство"

Начнем с исходных двух массивов из вопроса a и b:

int[] a = {6, 5, 6, 3, 4, 2};
int[] b = {5, 7, 6, 6, 2, 3, 4};

Мы скажем здесь, что более короткий массив имеет длину n, тогда более длинный массив должен иметь длину n + 1. Первым шагом к доказательству линейной сложности является объединение массивов в третий массив (мы будем называть его c):

int[] c = {6, 5, 6, 3, 4, 2, 5, 7, 6, 6, 2, 3, 4};

длина которого 2n + 1. Зачем это делать? Итак, теперь у нас есть еще одна проблема целиком: поиск элемента, который встречается нечетным числом раз в c (отсюда "нечетное число раз" и "уникальное" воспринимается как одно и то же). Это на самом деле довольно популярный вопрос интервью, и, по-видимому, мой учитель получил представление о своей проблеме, так что теперь мой вопрос имеет практическое значение. Ура!

Предположим, что существует алгоритм быстрее O (n), такой как O (log n). Это означает, что он получит доступ только к некоторым элементам c. Например, алгоритму O (log n) может потребоваться только проверить log (13) ~ 4 элементов в нашем массиве примеров, чтобы определить уникальный элемент. Наш вопрос: возможно ли это?

Сначала давайте посмотрим, удастся ли нам удалить какой-либо из элементов ( "удалив", я имею в виду, что вам не нужен доступ). Как насчет того, удалим ли мы 2 элемента, чтобы наш алгоритм проверял только подрамник c с длиной 2n - 1? Это все еще линейная сложность, но если мы сможем это сделать, возможно, мы сможем улучшить ее еще больше.

Итак, выберем два элемента c полностью случайным образом для удаления. На самом деле есть несколько вещей, которые могут произойти здесь, которые я обобщу в следующих случаях:

// Case 1: Remove two identical elements
{6, 5, 6, 3, 4, 2, 5, 7, 2, 3, 4};

// Case 2: Remove the unique element and one other element
{6, 6, 3, 4, 2, 5, 6, 6, 2, 3, 4};

// Case 3: Remove two different elements, neither of which are unique
{6, 5, 6, 4, 2, 5, 7, 6, 6, 3, 4};

Как выглядит наш массив? В первом случае 7 по-прежнему является единственным элементом. Во втором случае есть новый уникальный элемент, 5. И в третьем случае есть 3 уникальных элемента... да, это полный беспорядок там.

Теперь возникает вопрос: можем ли мы определить уникальный элемент c, просто посмотрев на этот подмассив? В первом случае мы видим, что 7 является единственным элементом подмассива, но мы не можем быть уверены, что он также является единственным элементом c; два удаленных элемента могли бы равняться 7 и 1. Аналогичный аргумент применим ко второму случаю. В случае 3 с 3 уникальными элементами мы не можем сказать, какие два не являются уникальными в c.

Становится ясным, что даже при доступе 2n - 1 для решения проблемы недостаточно информации. И поэтому оптимальное решение является линейным.

Конечно, реальное доказательство будет использовать индукцию, а не использовать доказательство, например, но я оставлю это кому-то еще:)

Ответ 3

Вы можете хранить количество каждого значения в коллекции, такое как массив или хэш-карта. O (n), то вы можете проверить значения другой коллекции и остановить, как только вы знаете, что у вас есть совпадение. Это может означать, что вы обычно выполняете поиск в среднем по половине второго массива.

Ответ 4

Это немного быстрее:

public static int getUniqueElement(int[] a, int[] b) {
    int ret = 0;
    int i;
    for (i = 0; i < a.length; i++) {
        ret += (a[i] - b[i]);
    }
    return Math.abs(ret - b[i]);
}

Это O (m), но порядок не рассказывает всю историю. Циклическая часть "официального" решения имеет около 3 * м + 3 * n операций, а немного более быстрое решение имеет 4 * м.

(подсчет цикла "i ++" и "i < a.length" как одна операция).

-Аль.

Ответ 5

Предполагая, что добавлен только один элемент, а массивы были идентичны для начала, вы можете нажать O (log (base 2) n).

Обоснование заключается в том, что любой массив подвергается поиску двоичного-вывода O (log n). За исключением того, что в этом случае вы не ищете значение в упорядоченном массиве, вы ищете первый элемент, не соответствующий совпадению. В таком случае [n] == b [n] означает, что вы слишком низки, а [n]!= B [n] означает, что вы можете быть слишком высокими, если только [n-1] == b [п-1].

Остальное - это базовый двоичный поиск. Проверьте средний элемент, определите, какое деление должно иметь ответ, и выполните под-поиск в этом разделе.

Ответ 6

Скажем, что есть два несортированных целочисленных массива a и b, с возможностью повторения элементов. Они идентичны (по содержащимся элементам) кроме один из массивов имеет дополнительный элемент..

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

В С# вы можете сделать это:

int[, , , , ,] a=new int[6, 5, 6, 3, 4, 2];
int[, , , , , ,] b=new int[5, 7, 6, 6, 2, 3, 4];
Console.WriteLine(b.Length/a.Length);

См? Независимо от дополнительного элемента, вы всегда будете знать это, просто разделив их длину.

С этими утверждениями мы не сохраняем данный ряд целых чисел как значения в массивах, а как их размеры.

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

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

Это всего лишь трюк, так как я думал, что этот вопрос - это трюк. Мы определенно не будем рассматривать его как решение для производства.

Ответ 7

Осторожно, неправильно использовать обозначение O (n + m). Существует только один параметр размера, который равен n (в асимптотическом смысле n и n + 1 равны). Вы должны просто сказать O (n). [При m > n + 1 проблема различна и сложнее.]

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

Все, что вы можете сделать, это уменьшить асимптотическую константу. Существует мало возможностей для улучшения, так как очевидные решения уже очень эффективны. Единственный цикл в (10), вероятно, трудно превзойти. Немного поразвлечь его следует улучшить (слегка), избегая ветки.

Если ваша цель - чистая производительность, вам следует обратиться к не переносным решениям, таким как векторизация (с использованием инструкций AXV, 8 ints за раз) и распараллеливание на multicores или GPGPU. В хорошем старом грязном C и 64-битном процессоре вы можете сопоставить данные с массивом из 64-битных int и xor элементов по две пары за раз;)

Ответ 8

Я думаю, что это похоже на Соответствие проблемы с гайками и болтами.

Вы можете достичь этого, возможно, в O (nlogn). Не уверен, что в этом случае меньше, чем O (n + m).

Ответ 9

Нет простого алгоритма. Те, что представлены в вопросе, находятся в O (n). Любой арифметический "трюк" для решения этого требует, чтобы по крайней мере каждый элемент обоих массивов читался один раз, поэтому мы остаемся в O (n) (или хуже).

Любая стратегия поиска, находящаяся в вещественном подмножестве O (n) (например, O (log n)), потребует сортированных массивов или некоторой другой сортированной структуры предварительной сборки (двоичное дерево, хеш). Все алгоритмы сортировки, известные человечеству, как минимум, O (n * log n) (Quicksort, Hashsort) в среднем хуже, чем O (n).

Поэтому, с математической точки зрения, алгоритма не существует быстрее. Могут быть некоторые оптимизации кода, но они не будут иметь большого значения, так как время выполнения будет линейным с длиной массива.