Для указанной задачи наиболее вероятно, что наиболее эффективным ответом является 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 раз, мы просто изменили 3 с на 5 с. Или мы можем сделать то же самое для 7, 11, 137, 727 или любого другого числа (включая четные числа). Но вместо фактического числа мы можем использовать любой его коэффициент, поэтому для 9 мы можем просто оставить его равным 3, а для четных чисел мы можем просто использовать 2 (и, следовательно, просто использовать xor).
Однако для исходной задачи не существует общего решения на основе подсчета битов, где число может повторяться любое нечетное количество раз. Это связано с тем, что даже если мы точно посчитаем биты без использования по модулю, когда мы смотрим на конкретный бит, мы просто не можем знать, представляет ли 9 раз, когда он появляется, 3 + 3 + 3 или 1 + 3 + 5. включается в три разных числа, каждое из которых появилось три раза, тогда оно должно быть отключено в нашем ответе. Если он был включен в число, которое появилось один раз, число, которое появилось три раза, и число, которое появилось пять раз, то это должно быть включено в нашем ответе. Но с помощью только количества битов мы не можем знать это.
Вот почему другой ответ не обобщает, и умная идея для обработки особых случаев не будет реализована: любая схема, основанная на взгляде на вещи постепенно, чтобы выяснить, какие биты должны быть включены или выключены, делает не обобщать. Учитывая это, я не думаю, что любая схема, которая занимает пространство O (1), работает для общего случая. Возможно, что есть умные схемы, которые используют O (LG N) пространство и т. Д., Но я бы сомневался в этом. Я думаю, что пространственный подход O (n), вероятно, является лучшим, что может быть сделано в предложенной задаче. Я не могу доказать это, но на данный момент, это то, что говорит мне мой инстинкт, и я надеюсь, что я, по крайней мере, убедил вас, что небольшие изменения в методе «четного числа» не помогут.