una - funcion eliminar en c++
Encontrar duplicados en O(n) tiempo y O(1) espacio (12)
Algoritmo se puede ver fácilmente en la siguiente función C. La recuperación de la matriz original, aunque no es necesaria, será posible tomando cada módulo de entrada 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'');
}
Ideone Link para probar.
Entrada: dada una matriz de n elementos que contiene elementos de 0 a n-1, con cualquiera de estos números apareciendo cualquier cantidad de veces.
Objetivo: encontrar estos números que se repiten en O (n) y usar solo espacio de memoria constante.
Por ejemplo, supongamos que n sea 7 y array sea {1, 2, 3, 1, 3, 0, 6}, la respuesta debería ser 1 y 3. Comprobé preguntas similares aquí, pero las respuestas usaron algunas estructuras de datos como HashSet etc.
Algún algoritmo eficiente para el mismo?
Aquí está el pseudocódigo
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
Aquí está la solución:
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]<<" ";
}
Esto es lo que se me ocurrió, que no requiere el bit de signo adicional:
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
El primer bucle permuta la matriz de modo que si el elemento x está presente al menos una vez, entonces una de esas entradas estará en la posición A[x] .
Tenga en cuenta que es posible que no se vea O (n) a primera vista, pero sí, aunque tiene un ciclo anidado, aún se ejecuta en O(N) tiempo. Un intercambio solo ocurre si hay una i tal que A[i] != i , y cada intercambio establece al menos un elemento tal que A[i] == i , donde eso no era verdadero antes. Esto significa que el número total de intercambios (y, por tanto, el número total de ejecuciones del cuerpo del ciclo while) es como máximo N-1 .
El segundo ciclo imprime los valores de x para los cuales A[x] no es igual a x , ya que el primer ciclo garantiza que si x existe al menos una vez en el conjunto, uno de esos casos estará en A[x] , esto significa que imprime esos valores de x que no están presentes en la matriz.
No es realmente bonito, pero al menos es fácil ver las propiedades O (N) y O (1). Básicamente escaneamos la matriz y, para cada número, vemos si la posición correspondiente ha sido marcada ya visto una vez (N) o ya visto varias veces (N + 1). Si está marcado ya visto una vez, lo imprimimos y lo marcamos ya visto varias veces. Si no está marcado, lo marcamos ya visto una vez y movemos el valor original del índice correspondiente a la posición actual (el marcado es una operación destructiva).
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;
}
}
o, mejor aún (más rápido, a pesar del doble bucle):
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;
}
}
}
Para N relativamente pequeño, podemos usar operaciones de 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
No C / C ++ pero de todos modos
Si la matriz no es demasiado grande, esta solución es más simple. Crea otra matriz del mismo tamaño para marcar.
1 Crea un mapa de bits / matriz del mismo tamaño que tu matriz de entrada
int check_list[SIZE_OF_INPUT];
for(n elements in checklist)
check_list[i]=0; //initialize to zero
2 escanee su matriz de entrada e incremente su recuento en la matriz anterior
for(i=0;i<n;i++) // every element in input array
{
check_list[a[i]]++; //increment its count
}
3 Ahora escanee el conjunto check_list e imprima el duplicado ya sea una vez o tantas veces que se hayan duplicado
for(i=0;i<n;i++)
{
if(check_list[i]>1) // appeared as duplicate
{
printf(" ",i);
}
}
Por supuesto, se necesita el doble de espacio consumido por la solución dada anteriormente, pero la eficiencia del tiempo es O (2n) que es básicamente O (n).
Supongamos que presentamos este conjunto como una estructura de datos de gráfico unidireccional: cada número es un vértice y su índice en el conjunto apunta a otro vértice que forma un borde del gráfico.
Para una mayor simplicidad, tenemos los índices 0 a n-1 y el rango de número desde 0..n-1. p.ej
0 1 2 3 4
a[3, 2, 4, 3, 1]
0 (3) -> 3 (3) es un ciclo.
Respuesta: simplemente recorra la matriz dependiendo de los índices. si a [x] = a [y] entonces es un ciclo y por lo tanto se duplica. Salte al siguiente índice y continúe de nuevo y así sucesivamente hasta el final de una matriz. Complejidad: O (n) tiempo y O (1) espacio.
Un pequeño código python para demostrar el método de caf anterior:
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] )
Una solución en C es:
#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;
}
Es O (n) el tiempo y O (1) la complejidad del espacio.
La brillante respuesta de caf imprime cada número que aparece k veces en la matriz k-1 veces. Ese es un comportamiento útil, pero la pregunta posiblemente requiera que cada duplicado se imprima una sola vez, y alude a la posibilidad de hacer esto sin soplar los límites de tiempo lineal / espacio constante. Esto se puede hacer reemplazando su segundo ciclo con el siguiente pseudocódigo:
for (i = 0; i < N; ++i) {
if (A[i] != i && A[A[i]] == A[i]) {
print A[i];
A[A[i]] = i;
}
}
Esto explota la propiedad de que después de que se ejecuta el primer bucle, si cualquier valor m aparece más de una vez, entonces se garantiza que una de esas apariencias está en la posición correcta, es decir, A[m] . Si tenemos cuidado, podemos usar esa ubicación "doméstica" para almacenar información sobre si se han impreso o no duplicados.
En la versión de caf, mientras revisábamos el conjunto, A[i] != i Implicaba que A[i] es un duplicado. En mi versión, confío en una invariante ligeramente diferente: que A[i] != i && A[A[i]] == A[i] implica que A[i] es un duplicado que no hemos visto antes . (Si deja caer la parte "que no hemos visto antes", puede verse que el resto está implícito en la verdad de la invariante de caf, y la garantía de que todos los duplicados tienen alguna copia en una ubicación de origen). Esta propiedad se mantiene en al principio (después de que termine el 1er bucle de caf) y muestro debajo que se mantiene después de cada paso.
A medida que avanzamos en la matriz, el éxito en la parte A[i] != i de la prueba implica que A[i] podría ser un duplicado que no se había visto antes. Si no lo hemos visto antes, entonces esperamos que la ubicación de origen de A[i] apunte a sí misma, eso es lo que se verifica en la segunda mitad de la condición if . Si ese es el caso, lo imprimimos y modificamos la ubicación de origen para señalar el primer duplicado encontrado, creando un "ciclo" de 2 pasos.
Para ver que esta operación no altera nuestro invariante, suponga que m = A[i] para una posición particular que satisface A[i] != i && A[A[i]] == A[i] . Es obvio que el cambio que hacemos ( A[A[i]] = i ) funcionará para evitar que otras apariciones de m no sean del hogar se emitan como duplicados al causar la falla de la segunda mitad de sus condiciones, pero ¿funcionará? cuando llego a la ubicación de casa, m ? Sí, lo hará, porque ahora, aunque en este nuevo i encontramos que la primera mitad de la condición if , A[i] != i , es verdadera, la segunda mitad prueba si la ubicación a la que apunta es una ubicación de inicio y encuentra que no lo es. En esta situación, ya no sabemos si m o A[m] fue el valor duplicado, pero sabemos que de cualquier manera, ya se ha informado , porque se garantiza que estos 2 ciclos no aparecerán en el resultado del primer ciclo de caf. (Tenga en cuenta que si m != A[m] entonces exactamente uno de m A[m] ocurre más de una vez, y el otro no ocurre en absoluto).
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();
}