У вас есть массив, в котором каждое число повторяется нечетное число раз (но больше, чем однократное вхождение). Точно одно число появляется один раз. Как найти номер, который появляется только один раз?
e.g.: {1, 6, 3, 1, 1, 6, 6, 9, 3, 3, 3, 3}
Ответ: 9.
Я думал о наличии хэш-таблицы, а затем просто подсчитывал элемент, чей счет равен 1. Это кажется тривиальным, и я не использую тот факт, что каждый другой элемент повторяется нечетно. Есть ли лучший подход.
Я считаю, что вы все еще можете использовать базовую идею XOR для решения этой проблемы умным способом.
Во-первых, позвольте мне изменить проблему, чтобы одно число появлялось один раз, а все остальные цифры отображались три раза.
Алгоритм:
Здесь A - массив длины n:
int ones = 0;
int twos = 0;
int not_threes, x;
for (int i=0; i<n; ++i) {
x = A[i];
twos |= ones & x;
ones ^= x;
not_threes = ~(ones & twos);
ones &= not_threes;
twos &= not_threes;
}
И элемент, который встречается ровно один раз, сохраняется в ones. Это использует время O(n) и O(1).
Я считаю, что я могу распространить эту идею на общий случай проблемы, но, возможно, один из вас может сделать это быстрее, поэтому я оставлю это сейчас и отредактирую его, когда и если я могу обобщить решение.
Объяснение:
Если проблема заключалась в следующем: "один элемент появляется один раз, а все остальные равно четное число раз", тогда решение будет состоять из элементов XOR. Причина в том, что x^x = 0, поэтому все парные элементы исчезнут, оставив только одинокий элемент. Если бы мы попробовали одну и ту же тактику здесь, мы бы оставили XOR разных элементов, чего мы не хотим.
Вместо этого алгоритм выше делает следующее:
ones - это XOR всех элементов, которые появились ровно один раз до сих пор.twos - это XOR всех элементов, которые оказались ровно вдвое до сих порКаждый раз, когда мы принимаем x как следующий элемент в массиве, есть три случая:
x, он XORed в onesx появился, он вынимается из ones (путем XORing его снова) и XORed в twosx, он вынимается из ones и twos.Следовательно, в конце, ones будет XOR всего одного элемента, одиночный элемент, который не повторяется. Есть 5 строк кода, которые нам нужно посмотреть, чтобы понять, почему это работает: пять после x = A[i].
Если это первый раз, когда x появился, то ones&x=ones, поэтому twos остается неизменным. Линия ones ^= x; XORs x с ones, как заявлено. Поэтому x находится точно в одном из ones и twos, поэтому в последних трех строках ничего не происходит ни с ones, ни с twos.
Если это второй раз x, то ones уже имеет x (по приведенному выше объяснению), поэтому теперь twos получает его с линией twos |= ones & x;. Кроме того, поскольку ones имеет x, строка ones ^= x; удаляет x из ones (потому что x^x=0). Опять же, последние три строки ничего не делают, так как точно один из ones и twos теперь имеет x.
Если это третий раз, когда появился x, тогда ones не имеет x, а twos. Итак, первая строка пусть twos держит x, а вторая добавляет x к ones. Теперь, поскольку оба ones и twos имеют x, последние три строки удаляют x из обоих.
Обобщение:
Если некоторые цифры появляются 5 раз, то этот алгоритм все еще работает. Это связано с тем, что появляется 4-й раз x, он не находится ни в ones, ни twos. Первые две строки добавляют x в ones, а не twos, а последние три строки ничего не делают. Появится 5-е время x, оно находится в ones, но не twos. Первая строка добавляет ее к twos, вторая удаляет ее из ones, а последние три строки ничего не делают.
Проблема в том, что появляется 6-й раз x, он берется из ones и twos, поэтому он возвращается к ones на 7-м проходе. Я пытаюсь придумать умный способ предотвратить это, но до сих пор я опустошаюсь.
Для указанной проблемы наиболее вероятно, что наиболее эффективным ответом является ответ O (n) пространства. С другой стороны, если мы сузим проблему как "Все числа появляются в n раз, кроме одного, который появляется только один раз" или даже "Все числа выглядят кратно n раз, за исключением одного, которое появляется только один раз", тогда существует довольно простая решение для любого n (более 1, очевидно), которое принимает только O (1) пространство, которое должно разбивать каждое число на биты, а затем подсчитывать, сколько раз каждый бит включается и принимать этот модуль n. Если результат равен 1, он должен быть включен в ответ. Если он равен 0, его следует отключить. (Любой другой ответ показывает, что параметры проблемы не выполнялись). Если мы рассмотрим ситуацию, когда n равно 2, мы видим, что использование XOR делает именно это (побитовое дополнение по модулю 2). Мы просто обобщаем вещи для побитового сложения по модулю n для других значений n.
Это, кстати, то, что делает другой ответ для n = 3, это на самом деле просто сложный способ поэтапного добавления, где он хранит 2-битный счет для каждого бита. В int, называемом "ones", содержится бит, и int, называемый "twos", содержит бит двоичного значения. Int not_threes используется для того, чтобы оба бита возвращались к нулю, когда счетчик достигает 3, таким образом, считая биты по модулю 3, а не обычно (что было бы по модулю 4, так как бит обертывался). Самый простой способ понять его код - это как 2-битный аккумулятор с дополнительной частью, чтобы заставить его работать по модулю 3.
Итак, для случая, когда все числа появляются кратно в 3 раза, кроме единственного числа, мы можем написать следующий код для 32-битных целых чисел:
int findUnique(int A[], int size) {
// First we set up a bit vector and initialize it to 0.
int count[32];
for (int j=0;j<32;j++) {
count[j] = 0;
}
// Then we go through each number in the list.
for (int i=0;i<size;i++) {
int x = A[i];
// And for each number we go through its bits one by one.
for (int j=0;j<32;j++) {
// We add the bit to the total.
count[j] += x & 1;
// And then we take it modulo 3.
count[j] %= 3;
x >>= 1;
}
}
// Then we just have to reassemble the answer by putting together any
// bits which didn't appear a multiple of 3 times.
int answer = 0;
for (int j=31;j>=0;j--) {
answer <<= 1;
if (count[j] == 1) {
answer |= 1;
}
}
return answer;
}
Этот код немного длиннее другого ответа (и внешне выглядит более сложным из-за дополнительных циклов, но каждый из них постоянный), но, мы надеемся, легче понять. Очевидно, что мы могли бы уменьшить пространство памяти, упаковывая биты более плотно, так как мы никогда не используем более двух из них для любого числа в подсчете. Но я не потрудился это сделать, поскольку это не влияет на асимптотическую сложность.
Если мы хотим изменить параметры проблемы, чтобы вместо этого числа повторялись 5 раз, мы просто изменяем 3s на 5s. Или мы можем сделать то же самое для 7, 11, 137, 727 или любого другого номера (включая четные числа). Но вместо того, чтобы использовать фактическое число, мы можем использовать любой его фактор, поэтому для 9 мы могли бы просто оставить его как 3, а для четных чисел мы можем просто использовать 2 (и, следовательно, просто использовать xor).
Однако для исходной задачи не существует общего решения для подсчета битов, где число может повторяться любое нечетное число раз. Это связано с тем, что даже если мы вычисляем бит точно, не используя по модулю, когда мы смотрим на конкретный бит, мы просто не можем знать, отображает ли оно 9 раз 3 + 3 + 3 или 1 + 3 + 5. Если бы это было включали три разных числа, каждый из которых появлялся три раза, тогда он должен быть отключен в нашем ответе. Если он был включен в число, которое появилось один раз, число, которое появилось три раза, а число, которое появилось пять раз, тогда оно должно быть включено в наш ответ. Но с учетом количества бит это невозможно для нас знать.
Вот почему другой ответ не обобщается, и разумная идея справиться с особыми случаями не будет реализована: любая схема, основанная на просмотре вещей побитно, чтобы выяснить, какие биты должны быть включены или выключены не обобщать. Учитывая это, я не думаю, что любая схема, которая занимает пространство O (1), работает для общего случая. Возможно, существуют умные схемы, которые используют O (lg n) пространство или так далее, но я бы сомневался в этом. Я думаю, что подход O (n) пространства, вероятно, лучший, что можно сделать в задаче, как было предложено. Я не могу это доказать, но на данный момент это то, что говорит мне моя кишка, и я надеюсь, что, по крайней мере, убедил вас в том, что небольшие хитрости к методу "четного числа" не будут сокращать ее.
Я знаю, что подтекст этого вопроса состоит в том, чтобы найти эффективное или результативное решение, но я думаю, что самый простой, читаемый код имеет много общего и в большинстве случаев его более чем достаточно.
Итак, как насчет этого:
var value = (new [] { 1, 6, 3, 1, 1, 6, 6, 9, 3, 3, 3, 3, })
.ToLookup(x => x)
.Where(xs => xs.Count() == 1)
.First()
.Key;
Старый добрый LINQ.: -)
Тест-показатель 100% с помощью С#
using System;
using System.Collections.Generic;
// you can also use other imports, for example:
// using System.Collections.Generic;
// you can write to stdout for debugging purposes, e.g.
// Console.WriteLine("this is a debug message");
class Solution {
public int solution(int[] A) {
Dictionary<int, int> dic =new Dictionary<int, int>();
foreach(int i in A)
{
if (dic.ContainsKey(i))
{
dic[i]=dic[i]+1;
}
else
{
dic.Add(i, 1);
}
}
foreach(var d in dic)
{
if (d.Value%2==1)
{
return d.Key;
}
}
return -1;
}
}
Java, корректность 100%, производительность 100%, оценка задачи 100%
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
import java.util.HashMap;
class Solution {
/*Simple solution
Will be using HashMap(for performance) as Array,
only Key set is needed.
Initially tried with ArryList but there was performance issue with
that so switch to HashMap.
Iterate over the given array and if item is there in key set
remove it(coz you found your pair) otherwise add as new Key.
After full Iteration only one key will be there in the Map that is
your solution.
In Short: If pair is found, remove it from Map Key set,
Last Key will be your solution
*/
public int solution(int[] A) {
//Map but used as Array
final HashMap<Integer, Boolean> mapHave = new HashMap<>();
//Iterate over given Array
for (int nIdx = 0; nIdx < A.length; nIdx++) {
//Current Item
Integer nVal = A[nIdx];
//Try to remove the current item, if item does not exists will
//return null and if condition will be true
if (mapHave.remove(nVal) == null) {
//current item not found, add it
mapHave.put(nVal, Boolean.TRUE);
}
}
//There will be only one key remaining in the Map, that is
//your solution
return mapHave.keySet().iterator().next();
}
}
Тест-показатель 100% в Python
def solution(A):
n = len(A)
if(A is None or n == 0):
return 0
if(n == 1):
return A[0]
result = 0
for i in range(0, n):
result ^= A[i]
return result