Вход: задан массив из n элементов, содержащий элементы от 0 до n-1, причем любое из этих чисел появляется сколько угодно раз.
Цель: найти эти повторяющиеся числа в O (n) и использовать только постоянное пространство памяти.
Например, пусть n равно 7, а array - {1, 2, 3, 1, 3, 0, 6}, ответ должен быть 1 и 3.
Я проверил подобные вопросы, но ответы использовали некоторые структуры данных, такие как HashSet и т.д.
Любой эффективный алгоритм для того же самого?
Это то, к чему я пришел, что не требует дополнительного бита знака:
for i := 0 to n - 1
while A[A[i]] != A[i]
swap(A[i], A[A[i]])
end while
end for
for i := 0 to n - 1
if A[i] != i then
print A[i]
end if
end for
Первый цикл переставляет массив так, что если элемент x присутствует хотя бы один раз, то одна из этих записей будет находиться в позиции A[x].
Обратите внимание, что он может не выглядеть O (n) сначала краснеть, но он - хотя он имеет вложенный цикл, он все еще работает в O(N) времени. Обмен происходит только в том случае, если существует i такой, что A[i] != i, и каждая подкачка устанавливает по крайней мере один элемент таким образом, что A[i] == i, если раньше это не было истинным. Это означает, что общее количество свопов (и, следовательно, общее количество выполнений тела цикла while) не превышает N-1.
Второй цикл печатает значения x, для которых A[x] не равно x - поскольку первый цикл гарантирует, что если x существует хотя бы один раз в массиве, один из этих экземпляров будет at A[x], это означает, что он печатает те значения x, которые отсутствуют в массиве.
блестящий ответ кафе печатает каждое число, которое появляется k раз в массиве k-1 раз. Это полезное поведение, но вопрос, возможно, требует, чтобы каждый дубликат печатался только один раз, и он намекает на возможность сделать это, не вызывая линейные границы времени/постоянного пространства. Это можно сделать, заменив его второй цикл следующим псевдокодом:
for (i = 0; i < N; ++i) {
if (A[i] != i && A[A[i]] == A[i]) {
print A[i];
A[A[i]] = i;
}
}
Это свойство использует свойство, которое после первого цикла запускается, если какое-либо значение m появляется более одного раза, то гарантируется, что одно из этих явлений находится в правильном положении, а именно A[m]. Если мы будем осторожны, мы сможем использовать это "домашнее" местоположение для хранения информации о том, были ли какие-либо дубликаты напечатаны или нет.
В версии caf, когда мы прошли через массив, A[i] != i подразумевал, что A[i] является дубликатом. В моей версии я полагаюсь на немного отличающийся инвариант: что A[i] != i && A[A[i]] == A[i] подразумевает, что A[i] является дубликатом, который мы не видели раньше. (Если вы отбросите часть, которую мы еще не видели раньше, все остальное будет видно из истины инварианта caf и гарантии того, что все дубликаты имеют некоторую копию в домашнем местоположении.) Это свойство сохраняется в (после завершения первого цикла петли), и я показываю ниже, что он поддерживается после каждого шага.
Когда мы проходим через массив, успех в части A[i] != i теста подразумевает, что A[i] может быть дубликатом, который ранее не был замечен. Если мы этого не видели раньше, то мы ожидаем, что домашнее местоположение A[i] укажет на себя - то, что тестировалось во второй половине условия if. Если это произойдет, мы напечатаем его и изменим исходное местоположение, чтобы указать на этот первый найденный дубликат, создав двухэтапный "цикл".
Чтобы убедиться, что эта операция не изменяет нашего инварианта, предположим, что m = A[i] для конкретной позиции i, удовлетворяющей A[i] != i && A[A[i]] == A[i]. Очевидно, что изменение, которое мы делаем (A[A[i]] = i), будет работать, чтобы предотвратить вывод других не-домашних входов m в виде дубликатов, вызвав потерю второй половины их условий if, но будет ли работать, когда i прибывает в исходное положение, m? Да, это произойдет, потому что теперь, хотя в этом новом i мы обнаруживаем, что 1-я половина условия if, A[i] != i, истинна, вторая половина проверяет, является ли местоположение, на которое оно указывает, домашним местоположением и считает, что это не так. В этой ситуации мы уже не знаем, было ли m или A[m] дублирующее значение, но мы знаем, что в любом случае это уже было сообщено, поскольку эти 2-циклы гарантированно не появятся в результате первого цикла caf, (Заметим, что если m != A[m], то ровно один из m и A[m] встречается более одного раза, а другой вообще не встречается.)
Вот псевдокод
for i <- 0 to n-1:
if (A[abs(A[i])]) >= 0 :
(A[abs(A[i])]) = -(A[abs(A[i])])
else
print i
end for
"Откуда появился этот вопрос? Интервью?"
Я помню, что у меня был случай, который включал операции с матрицей A[m][n], распределенной между процессорами p, где мне нужно было выбрать s лучшие столбцы из каждой локальной матрицы, затем поменять столбцы на все остальные и повторить в двоичном древе. Конечно, синхронизация была ключевым фактором, поэтому я использовал массив индексов для столбцов, поэтому в конце я мог вспомнить, какие столбцы мне нужны для обмена между процессорами.
Я считаю, что я пришел к тому же решению, что и в ответе в кафе, но почему-то мне не хватило времени, чтобы доказать, что он действительно работает, поэтому я, наконец, отступил на использование O (n) пространства.
Таким образом, это может определенно происходить на практике, особенно при использовании массивов индексов (поскольку они должны содержать только значения от 0 до n-1).
(извините за публикацию этого ответа, но, смешно, у меня нет права оставлять комментарий еще)
При относительно малых N мы можем использовать операции div/mod
n.times do |i|
e = a[i]%n
a[e] += n
end
n.times do |i|
count = a[i]/n
puts i if count > 1
end
Не C/С++, но в любом случае
Не очень красиво, но, по крайней мере, легко увидеть свойства O (N) и O (1). В основном мы сканируем массив, и для каждого числа мы видим, что соответствующая позиция была отмечена уже увиденным-раз (N) или уже увиденным-многократно (N + 1). Если он отмечен уже увиденным один раз, мы печатаем его и отмечаем его уже увиденным-многократно. Если он не помечен, мы отмечаем его уже увиденное-один раз, и мы переносим исходное значение соответствующего индекса в текущую позицию (помечение является деструктивной операцией).
for (i=0; i<a.length; i++) {
value = a[i];
if (value >= N)
continue;
if (a[value] == N) {
a[value] = N+1;
print value;
} else if (a[value] < N) {
if (value > i)
a[i--] = a[value];
a[value] = N;
}
}
или, еще лучше (быстрее, несмотря на двойной цикл):
for (i=0; i<a.length; i++) {
value = a[i];
while (value < N) {
if (a[value] == N) {
a[value] = N+1;
print value;
value = N;
} else if (a[value] < N) {
newvalue = value > i ? a[value] : N;
a[value] = N;
value = newvalue;
}
}
}
Одно из решений в C:
#include <stdio.h>
int finddup(int *arr,int len)
{
int i;
printf("Duplicate Elements ::");
for(i = 0; i < len; i++)
{
if(arr[abs(arr[i])] > 0)
arr[abs(arr[i])] = -arr[abs(arr[i])];
else if(arr[abs(arr[i])] == 0)
{
arr[abs(arr[i])] = - len ;
}
else
printf("%d ", abs(arr[i]));
}
}
int main()
{
int arr1[]={0,1,1,2,2,0,2,0,0,5};
finddup(arr1,sizeof(arr1)/sizeof(arr1[0]));
return 0;
}
Это O (n) время и O (1) пространственная сложность.
Предположим, что мы представляем этот массив как однонаправленную структуру данных графа - каждое число является вершиной, а его индекс в массиве указывает на другую вершину, образующую ребро графа.
Для еще большей простоты мы имеем индексы от 0 до n-1 и диапазон чисел от 0..n-1. например
0 1 2 3 4
a[3, 2, 4, 3, 1]
0 (3) → 3 (3) - цикл.
Ответ. Просто переходите массив, полагающийся на индексы. если a [x] = a [y], то это цикл и, следовательно, дублирует. Перейдите к следующему индексу и продолжайте снова и так далее до конца массива. Сложность: O (n) время и O (1) пространство.
Маленький код на Python, чтобы продемонстрировать метод caf выше:
a = [3, 1, 1, 0, 4, 4, 6]
n = len(a)
for i in range(0,n):
if a[ a[i] ] != a[i]: a[a[i]], a[i] = a[i], a[a[i]]
for i in range(0,n):
if a[i] != i: print( a[i] )
Алгоритм можно легко увидеть в следующей функции C. Извлечение исходного массива, хотя и не требуется, будет возможно с каждой записью по модулю n.
void print_repeats(unsigned a[], unsigned n)
{
unsigned i, _2n = 2*n;
for(i = 0; i < n; ++i) if(a[a[i] % n] < _2n) a[a[i] % n] += n;
for(i = 0; i < n; ++i) if(a[i] >= _2n) printf("%u ", i);
putchar('\n');
}
static void findrepeat()
{
int[] arr = new int[7] {0,2,1,0,0,4,4};
for (int i = 0; i < arr.Length; i++)
{
if (i != arr[i])
{
if (arr[i] == arr[arr[i]])
{
Console.WriteLine(arr[i] + "!!!");
}
int t = arr[i];
arr[i] = arr[arr[i]];
arr[t] = t;
}
}
for (int j = 0; j < arr.Length; j++)
{
Console.Write(arr[j] + " ");
}
Console.WriteLine();
for (int j = 0; j < arr.Length; j++)
{
if (j == arr[j])
{
arr[j] = 1;
}
else
{
arr[arr[j]]++;
arr[j] = 0;
}
}
for (int j = 0; j < arr.Length; j++)
{
Console.Write(arr[j] + " ");
}
Console.WriteLine();
}
Я быстро создал одно приложение для игровых площадок для поиска дубликатов за 0 (n) временную сложность и постоянное дополнительное пространство. Пожалуйста, проверьте URL Поиск дубликатов
IMP Вышеупомянутое решение работало, когда массив содержит элементы от 0 до n-1, причем любое из этих чисел появляется любое количество раз.
Вот решение:
using namespace std;
sort(vec.begin(),vec.end());
for(int i = 1; i<static_cas<int>(vec.size()); i++){
if(vec[i] == vec[i-1]) cout<<vec[i]<<" ";
}
Я не думаю, что это можно было бы решить в O (n) раз, пока данный массив чисел не будет отсортирован. Если массив отсортирован, этот код может печатать повторяющиеся числа в O (n) time.Here мой код
#include <iostream>
#include <string>
using namespace std;
int main ()
{
int q[]={1,1,3,4,4,7,7,5,6,6};
int arr_size=sizeof(q)/sizeof(q[0]),printed=0;
int c=q[0]; //saving the value of first element of array
for (int i=1;i<arr_size;i++)
{
if(c==q[i]) // checking whether the next element is same as pervious one or not
{if(printed!=1) //if yes then check whether no is already printed or not
{
cout<<c<<endl; // print the number
printed=1; // check bit number to check whether number is printed or not
}
}
else
{ c=q[i]; //saving the next new number of array
printed=0; //resetting the checking bit
}
}
system("PAUSE");
return EXIT_SUCCESS;
}
Как вы можете видеть здесь, я прошел сортированный массив. Таким образом, сложность времени для этого кода будет O (n), потому что существует только один цикл [1..n-1]. Если массив не будет отсортирован, тогда мы должны сначала отсортировать его, что займет время O (nLogn) [Best], используя быстрый или кучный сортировку. Вы можете проверить это на ideone
Если массив не слишком велик, это решение проще, Он создает другой массив одинакового размера для тикания.
1 Создайте растровое изображение/массив того же размера, что и ваш входной массив
int check_list[SIZE_OF_INPUT];
for(n elements in checklist)
check_list[i]=0; //initialize to zero
2 сканируйте свой входной массив и увеличьте его количество в указанном выше массиве
for(i=0;i<n;i++) // every element in input array
{
check_list[a[i]]++; //increment its count
}
3 Теперь отсканируйте массив check_list и распечатайте дубликат один или несколько раз, когда они были дублированы.
for(i=0;i<n;i++)
{
if(check_list[i]>1) // appeared as duplicate
{
printf(" ",i);
}
}
Конечно, это занимает в два раза больше пространства, затраченного на решение, приведенное выше, но эффективность времени равна O (2n), которая в основном O (n).