Существует массив размера n (числа от 0 до n - 3), и повторяются только 2 числа. Элементы помещаются случайным образом в массив.
например. в {2, 3, 6, 1, 5, 4, 0, 3, 5} n = 9, а повторные числа - 3 и 5.
Каков наилучший способ поиска повторяющихся номеров?
P.S. [Вы не должны использовать сортировку]
Существует O (n) решение, если вы знаете, что такое возможный домен ввода. Например, если ваш входной массив содержит числа от 0 до 100, рассмотрите следующий код.
bool flags[100];
for(int i = 0; i < 100; i++)
flags[i] = false;
for(int i = 0; i < input_size; i++)
if(flags[input_array[i]])
return input_array[i];
else
flags[input_array[i]] = true;
Конечно, есть дополнительная память, но это самый быстрый.
ОК, кажется, я просто не могу дать ему отдохнуть:)
int A[N] = {...};
int signed_1(n) { return n%2<1 ? +n : -n; } // 0,-1,+2,-3,+4,-5,+6,-7,...
int signed_2(n) { return n%4<2 ? +n : -n; } // 0,+1,-2,-3,+4,+5,-6,-7,...
long S1 = 0; // or int64, or long long, or some user-defined class
long S2 = 0; // so that it has enough bits to contain sum without overflow
for (int i=0; i<N-2; ++i)
{
S1 += signed_1(A[i]) - signed_1(i);
S2 += signed_2(A[i]) - signed_2(i);
}
for (int i=N-2; i<N; ++i)
{
S1 += signed_1(A[i]);
S2 += signed_2(A[i]);
}
S1 = abs(S1);
S2 = abs(S2);
assert(S1 != S2); // this algorithm fails in this case
p = (S1+S2)/2;
q = abs(S1-S2)/2;
Одна сумма (S1 или S2) содержит p и q с тем же знаком, другая сумма - с противоположными знаками, все остальные члены исключены. S1 и S2 должны иметь достаточное количество бит для размещения сумм, алгоритм не выдерживает переполнения из-за abs().
если abs (S1) == abs (S2), то алгоритм терпит неудачу, хотя это значение будет по-прежнему являться разницей между p и q (т.е. abs (p - q) == abs (S1)).
Я сомневаюсь, что кто-нибудь столкнется с такой проблемой в этой области;)
и я думаю, я знаю ожидаемое учителем:
Давайте возьмем массив {0,1,2,..., n-2, n-1},
Данную можно получить, заменив последние два элемента n-2 и n-1 неизвестными p и q (меньший порядок)
поэтому сумма элементов будет (n-1) n/2 + p + q - (n-2) - (n-1)
сумма квадратов (n-1) n (2n-1)/6 + p ^ 2 + q ^ 2 - (n-2) ^ 2 - (n-1) ^ 2
Простая математика остается:
(1) p+q = S1
(2) p^2+q^2 = S2
Конечно, вы не решите его, так как математические классы учат решать уравнения квадрата.
Сначала вычислите все по модулю 2 ^ 32, то есть допустим переполнение.
Затем проверьте пары {p, q}: {0, S1}, {1, S1-1}... против выражения (2), чтобы найти кандидатов (может быть больше 2 из-за модуляции и квадратизации)
И, наконец, проверьте найденные кандидаты, если они действительно присутствуют в массиве дважды.
Вы знаете, что ваш массив содержит все числа от 0 до n-3 и два повторяющихся (p и q). Для простоты, пока не будем игнорировать 0-й случай.
Вы можете рассчитать сумму и продукт по массиву, в результате чего:
1 + 2 + ... + n-3 + p + q = p + q + (n-3)(n-2)/2
Итак, если вы вычитаете (n-3) (n-2)/2 из суммы всего массива, вы получаете
sum(Array) - (n-3)(n-2)/2 = x = p + q
Теперь сделайте то же самое для продукта:
1 * 2 * ... * n - 3 * p * q = (n - 3)! * p * q
prod(Array) / (n - 3)! = y = p * q
Теперь вы получили следующие условия:
x = p + q
y = p * q
=> y(p + q) = x(p * q)
Если вы преобразуете этот термин, вы должны иметь возможность вычислить p и q
Возможно, вы сможете воспользоваться тем фактом, что sum (array) = (n-2) * (n-3)/2 + два недостающих номера.
Изменить: как отметили другие, в сочетании с суммой квадратов, вы можете использовать это, я был немного немного замешан в этом.
Вставьте каждый элемент в набор /hashtable, сначала проверив, если он уже в нем.
Проверьте эту старую, но хорошую бумагу по теме:
Некоторые ответы на вопрос: Алгоритм для определения того, содержит ли массив n... n + m? в качестве решения подзадачи, которое вы можете принять для своей цели.
Например, здесь соответствующая часть из моего ответа:
bool has_duplicates(int* a, int m, int n)
{
/** O(m) in time, O(1) in space (for 'typeof(m) == typeof(*a) == int')
Whether a[] array has duplicates.
precondition: all values are in [n, n+m) range.
feature: It marks visited items using a sign bit.
*/
assert((INT_MIN - (INT_MIN - 1)) == 1); // check n == INT_MIN
for (int *p = a; p != &a[m]; ++p) {
*p -= (n - 1); // [n, n+m) -> [1, m+1)
assert(*p > 0);
}
// determine: are there duplicates
bool has_dups = false;
for (int i = 0; i < m; ++i) {
const int j = abs(a[i]) - 1;
assert(j >= 0);
assert(j < m);
if (a[j] > 0)
a[j] *= -1; // mark
else { // already seen
has_dups = true;
break;
}
}
// restore the array
for (int *p = a; p != &a[m]; ++p) {
if (*p < 0)
*p *= -1; // unmark
// [1, m+1) -> [n, n+m)
*p += (n - 1);
}
return has_dups;
}
Программа оставляет массив неизменным (массив следует записывать, но его значения восстанавливаются при выходе).
Он работает для размеров массивов до INT_MAX (в 64-битных системах это 9223372036854775807).
suppose array is a[0], a[1], a[2] ..... a[n-1] sumA = a[0] + a[1] +....+a[n-1] sumASquare = a[0]*a[0] + a[1]*a[1] + a[2]*a[2] + .... + a[n]*a[n] sumFirstN = (N*(N+1))/2 where N=n-3 so sumFirstN = (n-3)(n-2)/2 similarly sumFirstNSquare = N*(N+1)*(2*N+1)/6 = (n-3)(n-2)(2n-5)/6 Suppose repeated elements are = X and Y so X + Y = sumA - sumFirstN; X*X + Y*Y = sumASquare - sumFirstNSquare; So on solving this quadratic we can get value of X and Y. Time Complexity = O(n) space complexity = O(1)
Я знаю, что вопрос очень старый, но я вдруг ударил его, и я думаю, что у меня есть интересный ответ на него. Мы знаем, что это головоломка и тривиальное решение (т.е. HashMap, Sort и т.д.), Независимо от того, насколько они хороши, будет скучно.
Поскольку числа являются целыми числами, они имеют постоянный размер бита (т.е. 32). Предположим, что мы работаем с 4-битными целыми числами прямо сейчас. Мы ищем A и B, которые являются повторяющимися числами.
Нам нужны 4 ведра, каждый на один бит. Каждое ведро содержит числа, для которых конкретный бит равен 1. Например, ведро 1 получает 2, 3, 4, 7,...:
Bucket 0 : Sum ( x where: x & 2 power 0 == 0 )
...
Bucket i : Sum ( x where: x & 2 power i == 0 )
Мы знаем, что было бы суммой каждого ведра, если бы не было дубликатов. Я рассматриваю это как предварительное знание.
После того, как генерируются выше ведра, куча из них будет иметь значения больше, чем ожидалось. Построим число из ведер, мы будем иметь (A OR B для вашей информации).
Мы можем вычислить (A XOR B) следующим образом:
A XOR B = Array[i] XOR Array[i-1] XOR ... 0, XOR n-3 XOR n-2 ... XOR 0
Теперь, возвращаясь к ведрам, мы точно знаем, какие ковши имеют оба наших номера, а у кого есть только один (из бит XOR).
Для ведер, имеющих только одно число, мы можем извлечь число num = (сумма - ожидаемая сумма ведра). Однако мы должны быть хорошими только в том случае, если мы сможем найти одно из повторяющихся чисел, поэтому, если у нас есть хотя бы один бит в XOR B, у нас есть ответ.
Но что, если A XOR B равно нулю? Ну, этот случай возможен только в том случае, если оба повторяющихся числа имеют одинаковое число, и тогда наш номер является ответом A OR B.
Сортировка массива будет лучшим решением. Простой вид затем сделает поиск тривиальным и займет намного меньше времени/пространства.
В противном случае, если вы знаете домен номеров, создайте в нем массив с таким количеством ведер и увеличите их каждый раз, когда вы пройдете через массив. что-то вроде этого:
int count [10];
for (int i = 0; i < arraylen; i++) {
count[array[i]]++;
}
Затем просто выполните поиск в массиве для любых чисел, превышающих 1. Это элементы с дубликатами. Требуется только один проход через исходный массив и один проход через массив count.
Здесь реализация в Python @eugensk00 отвечает (одна из ее ревизий), которая не использует модульную арифметику. Это однопроходный алгоритм, O (log (n)) в пространстве. Если используются целые числа с фиксированной шириной (например, 32-разрядные), для этого требуется только два числа с фиксированной шириной (например, для 32-разрядных: одно 64-разрядное число и одно 128-разрядное число). Он может обрабатывать произвольные большие целые последовательности (он считывает одно целое за раз, поэтому целая последовательность не требует наличия в памяти).
def two_repeated(iterable):
s1, s2 = 0, 0
for i, j in enumerate(iterable):
s1 += j - i # number_of_digits(s1) ~ 2 * number_of_digits(i)
s2 += j*j - i*i # number_of_digits(s2) ~ 4 * number_of_digits(i)
s1 += (i - 1) + i
s2 += (i - 1)**2 + i**2
p = (s1 - int((2*s2 - s1**2)**.5)) // 2
# `Decimal().sqrt()` could replace `int()**.5` for really large integers
# or any function to compute integer square root
return p, s1 - p
Пример:
>>> two_repeated([2, 3, 6, 1, 5, 4, 0, 3, 5])
(3, 5)
Более подробная версия приведенного выше кода приведена с объяснением:
def two_repeated_seq(arr):
"""Return the only two duplicates from `arr`.
>>> two_repeated_seq([2, 3, 6, 1, 5, 4, 0, 3, 5])
(3, 5)
"""
n = len(arr)
assert all(0 <= i < n - 2 for i in arr) # all in range [0, n-2)
assert len(set(arr)) == (n - 2) # number of unique items
s1 = (n-2) + (n-1) # s1 and s2 have ~ 2*(k+1) and 4*(k+1) digits
s2 = (n-2)**2 + (n-1)**2 # where k is a number of digits in `max(arr)`
for i, j in enumerate(arr):
s1 += j - i
s2 += j*j - i*i
"""
s1 = (n-2) + (n-1) + sum(arr) - sum(range(n))
= sum(arr) - sum(range(n-2))
= sum(range(n-2)) + p + q - sum(range(n-2))
= p + q
"""
assert s1 == (sum(arr) - sum(range(n-2)))
"""
s2 = (n-2)**2 + (n-1)**2 + sum(i*i for i in arr) - sum(i*i for i in range(n))
= sum(i*i for i in arr) - sum(i*i for i in range(n-2))
= p*p + q*q
"""
assert s2 == (sum(i*i for i in arr) - sum(i*i for i in range(n-2)))
"""
s1 = p+q
-> s1**2 = (p+q)**2
-> s1**2 = p*p + 2*p*q + q*q
-> s1**2 - (p*p + q*q) = 2*p*q
s2 = p*p + q*q
-> p*q = (s1**2 - s2)/2
Let C = p*q = (s1**2 - s2)/2 and B = p+q = s1 then from Viete theorem follows
that p and q are roots of x**2 - B*x + C = 0
-> p = (B + sqrtD) / 2
-> q = (B - sqrtD) / 2
where sqrtD = sqrt(B**2 - 4*C)
-> p = (s1 + sqrt(2*s2 - s1**2))/2
"""
sqrtD = (2*s2 - s1**2)**.5
assert int(sqrtD)**2 == (2*s2 - s1**2) # perfect square
sqrtD = int(sqrtD)
assert (s1 - sqrtD) % 2 == 0 # even
p = (s1 - sqrtD) // 2
q = s1 - p
assert q == ((s1 + sqrtD) // 2)
assert sqrtD == (q - p)
return p, q
ПРИМЕЧАНИЕ: вычисление целочисленного квадратного корня из числа (~ N ** 4) делает указанный алгоритм нелинейным.
Поскольку задан диапазон, вы можете выполнить сортировку по методу radix. Это сортирует ваш массив в O (n). Поиск дубликатов в отсортированном массиве - это O (n)
Вы можете использовать простой вложенный цикл
int[] numArray = new int[] { 1, 2, 3, 4, 5, 7, 8, 3, 7 };
for (int i = 0; i < numArray.Length; i++)
{
for (int j = i + 1; j < numArray.Length; j++)
{
if (numArray[i] == numArray[j])
{
//DO SOMETHING
}
}
* ИЛИ вы можете фильтровать массив и использовать рекурсивную функцию, если вы хотите получить счетчик вхождений *
int[] array = { 1, 2, 3, 4, 5, 4, 4, 1, 8, 9, 23, 4, 6, 8, 9, 1,4 };
int[] myNewArray = null;
int a = 1;
void GetDuplicates(int[] array)
for (int i = 0; i < array.Length; i++)
{
for (int j = i + 1; j < array.Length; j++)
{
if (array[i] == array[j])
{
a += 1;
}
}
Console.WriteLine(" {0} occurred {1} time/s", array[i], a);
IEnumerable<int> num = from n in array where n != array[i] select n;
myNewArray = null;
a = 1;
myNewArray = num.ToArray() ;
break;
}
GetDuplicates(myNewArray);
ответ на 18.. вы берете массив из 9, а элементы начинаются с 0... так что максимум ele будет 6 в вашем массиве. Возьмите сумму элементов от 0 до 6 и возьмите сумму элементов массива. вычислите их разницу (скажем, d). Это p + q. Теперь возьмите XOR элементов от 0 до 6 (скажем, x1). Теперь возьмите XOR элементов массива (скажем, x2). x2 - XOR всех элементов от 0 до 6, за исключением двух повторяющихся элементов, поскольку они отменяют друг друга. теперь для я = 0-6, для каждого элемента массива, скажем, p является элементом a [i], поэтому вы можете вычислить q, вычитая этот элемент из d. сделать XOR из p и q и XOR их с x2 и проверить, если x1 == x2. аналогично для всех элементов вы получите элементы, для которых это условие будет истинным, и вы делаете это в O (n). Продолжайте кодирование!
проверить это... O (n) и O (1) пространственная сложность
for(i=0;i< n;i++)
xor=xor^arr[i]
for(i=1;i<=n-3;i++)
xor=xor^i;
Итак, в данном примере вы получите xor of 3 и 5
xor=xor & -xor //Isolate the last digit
for(i = 0; i < n; i++)
{
if(arr[i] & xor)
x = x ^ arr[i];
else
y = y ^ arr[i];
}
for(i = 1; i <= n-3; i++)
{
if(i & xor)
x = x ^ i;
else
y = y ^ i;
}
x и y - ваши ответы
Для каждого числа: проверьте, существует ли он в остальной части массива.
Без сортировки вы будете отслеживать числа, которые вы уже посетили.
в psuedocode это будет в основном (так, чтобы я не просто дал вам ответ):
for each number in the list
if number not already in unique numbers list
add it to the unique numbers list
else
return that number as it is a duplicate
end if
end for each
Как насчет этого:
for (i=0; i<n-1; i++) {
for (j=i+1; j<n; j++) {
if (a[i] == a[j]) {
printf("%d appears more than once\n",a[i]);
break;
}
}
}
Конечно, это не самый быстрый, но простой и понятный, и требует нет дополнительной памяти. Если n - небольшое число, например 9 или 100, то это может быть "наилучшим". (т.е. "Лучшее" может означать разные вещи: быстрее всего выполнять, наименьший объем памяти, большинство поддерживаемых, наименее затратных для разработки и т.д.)
for(i=1;i<=n;i++) {
if(!(arr[i] ^ arr[i+1]))
printf("Found Repeated number %5d",arr[i]);
}
Я написал небольшую программу, в которой выясняется, что количество элементов не повторяется, просто пройдите через это, дайте мне знать ваше мнение, на данный момент я предполагаю, что даже число элементов равномерное, но может легко расширяться и для нечетных чисел.
Итак, моя идея состоит в том, чтобы сначала отсортировать числа, а затем применить мой алгоритм. Сортировка класса может использоваться для сортировки этих элементов.
Давайте возьмем входной массив, как показано ниже
int arr[] = {1,1,2,10,3,3,4,5,5,6,6};
числа 2,10 и 4 не повторяются, но они отсортированы по порядку, если не отсортированы, используйте быструю сортировку, чтобы сначала отсортировать ее.
Позволяет применить мою программу на этом
using namespace std;
main()
{
//int arr[] = {2, 9, 6, 1, 1, 4, 2, 3, 5};
int arr[] = {1,1,2,10,3,3,4,5,5,6,6};
int i = 0;
vector<int> vec;
int var = arr[0];
for(i = 1 ; i < sizeof(arr)/sizeof(arr[0]); i += 2)
{
var = var ^ arr[i];
if(var != 0 )
{
//put in vector
var = arr[i-1];
vec.push_back(var);
i = i-1;
}
var = arr[i+1];
}
for(int i = 0 ; i < vec.size() ; i++)
printf("value not repeated = %d\n",vec[i]);
}
Это дает результат:
value not repeated= 2
value not repeated= 10
value not repeated= 4
Простое и очень прямое, просто используйте XOR man.
В c:
int arr[] = {2, 3, 6, 1, 5, 4, 0, 3, 5};
int num = 0, i;
for (i=0; i < 8; i++)
num = num ^ arr[i] ^i;
Так как x^x=0, числа, которые повторяются нечетным числом раз, нейтрализуются. Позвольте называть уникальные числа a и b. Мы остаемся с a^b. Мы знаем a^b != 0, так как a != b. Выберите любой 1 бит a^b и используйте его как маску ie.choose x как мощность 2, так что x & (a^b) отличное от нуля.
Теперь разделим список на два подписок - один подсписок содержит все числа y с y&x == 0, а остальные - в другом подсписке. Кстати, мы выбрали x, мы знаем, что пары a и b находятся в разных ведрах. Таким образом, мы можем применить тот же самый метод, который был использован выше для каждого ведра независимо, и выяснить, что такое a и b.
Вот алгоритм, который использует статистику заказа и работает в O(n).
Вы можете решить эту проблему, нажимая SELECT со значением медианного параметра.
Вы также полагаетесь на то, что после вызова SELECT,
элементы, которые меньше или равны медианной, перемещаются влево от медианы.
SELECT на A со средой в качестве параметра.floor(n/2), то повторяющиеся значения соответствуют медиане. Итак, вы продолжаете правую половину массива.Например:
A={2, 3, 6, 1, 5, 4, 0, 3, 5} n=9, тогда медиана должна быть значением 4.SELECTA={3, 2, 0, 1, <3>, 4, 5, 6, 5} Среднее значение меньше 4, поэтому мы продолжаем левую половину.A={3, 2, 0, 1, 3}SELECTA={1, 0, <2>, 3, 3}, тогда медиана должна быть 2, и поэтому мы продолжаем правую половину.A={3, 3}, найдено.Этот алгоритм работает в O(n+n/2+n/4+...)=O(n).
Как насчет использования https://en.wikipedia.org/wiki/HyperLogLog?
Redis делает http://redis.io/topics/data-types-intro#hyperloglogs
HyperLogLog - это вероятностная структура данных, используемая для подсчета уникальных вещей (технически это относится к оценке мощности множества). Обычно подсчет уникальных предметов требует использования объема памяти, пропорционального количеству предметов, которые вы хотите подсчитать, потому что вам нужно помнить те элементы, которые вы уже видели в прошлом, чтобы не считать их несколько раз. Однако существует набор алгоритмов, которые торгуют памятью для точности: вы заканчиваете оценочную меру со стандартной ошибкой, в случае реализации Redis, которая составляет менее 1%. Магия этого алгоритма заключается в том, что вам больше не нужно использовать объем памяти, пропорциональный количеству подсчитанных элементов, и вместо этого можно использовать постоянный объем памяти! 12k байт в худшем случае или намного меньше, если ваш HyperLogLog (мы просто назовем их HLL с этого момента) видел очень мало элементов.
Почему мы должны пытаться выполнять математику (специально решая квадратичные уравнения), это дорогостоящие операционные системы. Лучший способ решить эту задачу: t построить битмап битов размера (n-3), т.е. (N -3) +7/8 байт. Лучше сделать calloc для этой памяти, поэтому каждый бит будет инициализирован до 0. Затем пройдите по списку и установите бит в 1, когда бит встречается, если бит уже установлен на 1, для которого нет, то это повторенное число. Это можно расширить, чтобы узнать, нет ли в массиве отсутствующего элемента или нет. Это решение O (n) по временной сложности