values - Algoritmo: forma eficiente de eliminar enteros duplicados de una matriz
how do you find the duplicate number on a given integer array (30)
¿Qué tal lo siguiente?
int* temp = malloc(sizeof(int)*len);
int count = 0;
int x =0;
int y =0;
for(x=0;x<len;x++)
{
for(y=0;y<count;y++)
{
if(*(temp+y)==*(array+x))
{
break;
}
}
if(y==count)
{
*(temp+count) = *(array+x);
count++;
}
}
memcpy(array, temp, sizeof(int)*len);
Intento declarar una matriz temporal y poner los elementos en eso antes de copiar todo a la matriz original.
Obtuve este problema de una entrevista con Microsoft.
Dada una matriz de enteros aleatorios, escriba un algoritmo en C que elimine los números duplicados y devuelva los números únicos en la matriz original.
Ej. Entrada: {4, 8, 4, 1, 1, 2, 9} Salida: {4, 8, 1, 2, 9, ?, ?}
Una advertencia es que el algoritmo esperado no debería requerir que la matriz se ordene primero. Y cuando un elemento ha sido eliminado, los siguientes elementos también deben desplazarse hacia adelante. De todos modos, el valor de los elementos en la cola de la matriz donde los elementos se desplazaron hacia adelante son insignificantes.
Actualización: El resultado debe ser devuelto en la matriz original y la estructura de datos auxiliares (por ejemplo, hashtable) no debe ser utilizada. Sin embargo, creo que la preservación de orden no es necesaria.
Actualización2: para aquellos que se preguntan por qué estas limitaciones poco prácticas, esta fue una pregunta de entrevista y todas estas limitaciones se discuten durante el proceso de pensamiento para ver cómo puedo llegar a diferentes ideas.
Aquí está mi solución.
///// find duplicates in an array and remove them
void unique(int* input, int n)
{
merge_sort(input, 0, n) ;
int prev = 0 ;
for(int i = 1 ; i < n ; i++)
{
if(input[i] != input[prev])
if(prev < i-1)
input[prev++] = input[i] ;
}
}
Aquí hay una versión de Java.
int[] removeDuplicate(int[] input){
int arrayLen = input.length;
for(int i=0;i<arrayLen;i++){
for(int j = i+1; j< arrayLen ; j++){
if(((input[i]^input[j]) == 0)){
input[j] = 0;
}
if((input[j]==0) && j<arrayLen-1){
input[j] = input[j+1];
input[j+1] = 0;
}
}
}
return input;
}
Bueno, su implementación básica es bastante simple. Repase todos los elementos, verifique si hay duplicados en los restantes y desplace el resto sobre ellos.
Es terriblemente ineficiente y podría acelerarlo mediante un conjunto de ayuda para la salida o los árboles de clasificación / binarios, pero esto no parece estar permitido.
Cree un BinarySearchTree que tenga O (n) complejidad.
Después de revisar el problema, esta es mi forma delphi, que puede ayudar
var
A: Array of Integer;
I,J,C,K, P: Integer;
begin
C:=10;
SetLength(A,10);
A[0]:=1; A[1]:=4; A[2]:=2; A[3]:=6; A[4]:=3; A[5]:=4;
A[6]:=3; A[7]:=4; A[8]:=2; A[9]:=5;
for I := 0 to C-1 do
begin
for J := I+1 to C-1 do
if A[I]=A[J] then
begin
for K := C-1 Downto J do
if A[J]<>A[k] then
begin
P:=A[K];
A[K]:=0;
A[J]:=P;
C:=K;
break;
end
else
begin
A[K]:=0;
C:=K;
end;
end;
end;
//tructate array
setlength(A,C);
end;
El siguiente ejemplo debería resolver su problema:
def check_dump(x):
if not x in t:
t.append(x)
return True
t=[]
output = filter(check_dump, input)
print(output)
True
El valor de retorno de la función debe ser el número de elementos únicos y todos están almacenados en la parte frontal de la matriz. Sin esta información adicional, ni siquiera sabrá si hubo duplicados.
Cada iteración del ciclo externo procesa un elemento de la matriz. Si es único, permanece en la parte frontal de la matriz y si es un duplicado, se sobrescribe con el último elemento no procesado en la matriz. Esta solución se ejecuta en O (n ^ 2) tiempo.
#include <stdio.h>
#include <stdlib.h>
size_t rmdup(int *arr, size_t len)
{
size_t prev = 0;
size_t curr = 1;
size_t last = len - 1;
while (curr <= last) {
for (prev = 0; prev < curr && arr[curr] != arr[prev]; ++prev);
if (prev == curr) {
++curr;
} else {
arr[curr] = arr[last];
--last;
}
}
return curr;
}
void print_array(int *arr, size_t len)
{
printf("{");
size_t curr = 0;
for (curr = 0; curr < len; ++curr) {
if (curr > 0) printf(", ");
printf("%d", arr[curr]);
}
printf("}");
}
int main()
{
int arr[] = {4, 8, 4, 1, 1, 2, 9};
printf("Before: ");
size_t len = sizeof (arr) / sizeof (arr[0]);
print_array(arr, len);
len = rmdup(arr, len);
printf("/nAfter: ");
print_array(arr, len);
printf("/n");
return 0;
}
En JAVA,
Integer[] arrayInteger = {1,2,3,4,3,2,4,6,7,8,9,9,10};
String value ="";
for(Integer i:arrayInteger)
{
if(!value.contains(Integer.toString(i))){
value +=Integer.toString(i)+",";
}
}
String[] arraySplitToString = value.split(",");
Integer[] arrayIntResult = new Integer[arraySplitToString.length];
for(int i = 0 ; i < arraySplitToString.length ; i++){
arrayIntResult[i] = Integer.parseInt(arraySplitToString[i]);
}
salida: {1, 2, 3, 4, 6, 7, 8, 9, 10}
espero que esto ayude
En Java lo resolvería así. No sé cómo escribir esto en C.
int length = array.length;
for (int i = 0; i < length; i++)
{
for (int j = i + 1; j < length; j++)
{
if (array[i] == array[j])
{
int k, j;
for (k = j + 1, l = j; k < length; k++, l++)
{
if (array[k] != array[i])
{
array[l] = array[k];
}
else
{
l--;
}
}
length = l;
}
}
}
Esta es la solución ingenua (N * (N-1) / 2). Utiliza un espacio adicional constante y mantiene el orden original. Es similar a la solución de @Byju, pero no usa bloques if(){} . También evita copiar un elemento sobre sí mismo.
#include <stdio.h>
#include <stdlib.h>
int numbers[] = {4, 8, 4, 1, 1, 2, 9};
#define COUNT (sizeof numbers / sizeof numbers[0])
size_t undup_it(int array[], size_t len)
{
size_t src,dst;
/* an array of size=1 cannot contain duplicate values */
if (len <2) return len;
/* an array of size>1 will cannot at least one unique value */
for (src=dst=1; src < len; src++) {
size_t cur;
for (cur=0; cur < dst; cur++ ) {
if (array[cur] == array[src]) break;
}
if (cur != dst) continue; /* found a duplicate */
/* array[src] must be new: add it to the list of non-duplicates */
if (dst < src) array[dst] = array[src]; /* avoid copy-to-self */
dst++;
}
return dst; /* number of valid alements in new array */
}
void print_it(int array[], size_t len)
{
size_t idx;
for (idx=0; idx < len; idx++) {
printf("%c %d", (idx) ? '','' :''{'' , array[idx] );
}
printf("}/n" );
}
int main(void) {
size_t cnt = COUNT;
printf("Before undup:" );
print_it(numbers, cnt);
cnt = undup_it(numbers,cnt);
printf("After undup:" );
print_it(numbers, cnt);
return 0;
}
Esto se puede hacer en una pasada con un algoritmo O (N log N) y sin almacenamiento adicional.
Proceda desde el elemento a[1] a a[N] . En cada etapa i , todos los elementos a la izquierda de a[i] comprenden un montón ordenado de elementos a[0] a a[j] . Mientras tanto, un segundo índice j , inicialmente 0, realiza un seguimiento del tamaño del montón.
Examine a[i] e insértelo en el montón, que ahora ocupa elementos de a[0] a a[j+1] . A medida que se inserta el elemento, si se encuentra un elemento duplicado a[k] con el mismo valor, no inserte a[i] en el montón (es decir, deséchelo); de lo contrario, insértelo en el montón, que ahora crece en un elemento y ahora comprende a[0] a a[j+1] , e incremente j .
Continúe de esta manera, incrementando i hasta que todos los elementos de la matriz se hayan examinado e insertado en el montón, que termina ocupando a[0] a a[j] . j es el índice del último elemento del montón, y el montón solo contiene valores de elementos únicos.
int algorithm(int[] a, int n)
{
int i, j;
for (j = 0, i = 1; i < n; i++)
{
// Insert a[i] into the heap a[0...j]
if (heapInsert(a, j, a[i]))
j++;
}
return j;
}
bool heapInsert(a[], int n, int val)
{
// Insert val into heap a[0...n]
...code omitted for brevity...
if (duplicate element a[k] == val)
return false;
a[k] = val;
return true;
}
Mirando el ejemplo, esto no es exactamente lo que se solicitó ya que la matriz resultante conserva el orden de los elementos originales. Pero si este requisito se relaja, el algoritmo anterior debería hacer el truco.
Esto se puede hacer en una sola pasada, en O (N) tiempo en el número de enteros en la lista de entrada, y O (N) almacenamiento en la cantidad de enteros únicos.
Recorra la lista de adelante hacia atrás, con dos punteros "dst" y "src" inicializados al primer elemento. Comience con una tabla hash vacía de "enteros vistos". Si el entero en src no está presente en el hash, escríbalo en la ranura en dst e incremente dst. Agregue el número entero en src al hash, luego incremente src. Repita hasta que src pase el final de la lista de entrada.
Inserte todos los elementos en un binary tree the disregards duplicates - O(nlog(n)) . Luego extraiga todos ellos de nuevo en la matriz haciendo un recorrido - O(n) . Supongo que no necesita preservación de orden.
Lo publiqué una vez antes en SO, pero lo reproduciré aquí porque es genial. Utiliza hash, construye algo así como un hash establecido en su lugar. Se garantiza que es O (1) en el espacio axilar (la recursión es una llamada de cola), y por lo general es una complejidad de tiempo O (N). El algoritmo es como sigue:
- Tome el primer elemento de la matriz, este será el centinela.
- Reordene el resto de la matriz, tanto como sea posible, de modo que cada elemento esté en la posición correspondiente a su hash. A medida que se completa este paso, se descubrirán duplicados. Establecerlos igual a centinela.
- Mueva todos los elementos cuyo índice es igual al hash al comienzo de la matriz.
- Mueva todos los elementos que son igual a centinela, excepto el primer elemento de la matriz, hasta el final de la matriz.
- Lo que queda entre los elementos hash correctamente y los elementos duplicados serán los elementos que no se pudieron colocar en el índice correspondiente a su hash debido a una colisión. Recurse para tratar con estos elementos.
Esto puede mostrarse como O (N) siempre que no haya un escenario patológico en el hash: incluso si no hay duplicados, aproximadamente 2/3 de los elementos se eliminarán en cada recursión. Cada nivel de recursión es O (n) donde n pequeña es la cantidad de elementos que quedan. El único problema es que, en la práctica, es más lento que un tipo rápido cuando hay pocos duplicados, es decir, muchas colisiones. Sin embargo, cuando hay una gran cantidad de duplicados, es increíblemente rápido.
Editar: en las implementaciones actuales de D, hash_t es de 32 bits. Todo sobre este algoritmo supone que habrá muy pocas colisiones hash, si las hay, en un espacio completo de 32 bits. Las colisiones pueden, sin embargo, ocurrir con frecuencia en el espacio del módulo. Sin embargo, esta suposición con toda probabilidad será cierta para cualquier conjunto de datos de tamaño razonable. Si la clave es menor o igual a 32 bits, puede ser su propio hash, lo que significa que una colisión en el espacio completo de 32 bits es imposible. Si es más grande, simplemente no puede encajar lo suficiente en el espacio de direcciones de memoria de 32 bits para que sea un problema. Supongo que hash_t se incrementará a 64 bits en implementaciones de 64 bits de D, donde los conjuntos de datos pueden ser más grandes. Además, si esto alguna vez resultó ser un problema, se podría cambiar la función hash en cada nivel de recursión.
Aquí hay una implementación en el lenguaje de programación D:
void uniqueInPlace(T)(ref T[] dataIn) {
uniqueInPlaceImpl(dataIn, 0);
}
void uniqueInPlaceImpl(T)(ref T[] dataIn, size_t start) {
if(dataIn.length - start < 2)
return;
invariant T sentinel = dataIn[start];
T[] data = dataIn[start + 1..$];
static hash_t getHash(T elem) {
static if(is(T == uint) || is(T == int)) {
return cast(hash_t) elem;
} else static if(__traits(compiles, elem.toHash)) {
return elem.toHash;
} else {
static auto ti = typeid(typeof(elem));
return ti.getHash(&elem);
}
}
for(size_t index = 0; index < data.length;) {
if(data[index] == sentinel) {
index++;
continue;
}
auto hash = getHash(data[index]) % data.length;
if(index == hash) {
index++;
continue;
}
if(data[index] == data[hash]) {
data[index] = sentinel;
index++;
continue;
}
if(data[hash] == sentinel) {
swap(data[hash], data[index]);
index++;
continue;
}
auto hashHash = getHash(data[hash]) % data.length;
if(hashHash != hash) {
swap(data[index], data[hash]);
if(hash < index)
index++;
} else {
index++;
}
}
size_t swapPos = 0;
foreach(i; 0..data.length) {
if(data[i] != sentinel && i == getHash(data[i]) % data.length) {
swap(data[i], data[swapPos++]);
}
}
size_t sentinelPos = data.length;
for(size_t i = swapPos; i < sentinelPos;) {
if(data[i] == sentinel) {
swap(data[i], data[--sentinelPos]);
} else {
i++;
}
}
dataIn = dataIn[0..sentinelPos + start + 1];
uniqueInPlaceImpl(dataIn, start + swapPos + 1);
}
Podrías hacer esto en un solo cruce, si estás dispuesto a sacrificar memoria. Simplemente puede contar si ha visto un número entero o no en una matriz hash / asociativa. Si ya has visto un número, quítalo sobre la marcha, o mejor aún, mueve los números que no has visto en una nueva matriz, evitando cualquier cambio en la matriz original.
En Perl:
foreach $i (@myary) {
if(!defined $seen{$i}) {
$seen{$i} = 1;
push @newary, $i;
}
}
Qué tal si:
void rmdup(int *array, int length)
{
int *current , *end = array + length - 1;
for ( current = array + 1; array < end; array++, current = array + 1 )
{
while ( current <= end )
{
if ( *current == *array )
{
*current = *end--;
}
else
{
current++;
}
}
}
}
Debería ser O (n ^ 2) o menos.
Si está buscando la notación O superior, luego ordenando la matriz con un orden O (n log n), entonces hacer un cruce O (n) puede ser la mejor ruta. Sin ordenar, estás mirando O (n ^ 2).
Editar: si solo está haciendo números enteros, también puede hacer radix sort para obtener O (n).
Si puede usar C ++, una llamada a std::sort seguida de una llamada a std::unique le dará la respuesta. La complejidad del tiempo es O (N log N) para el ordenamiento y O (N) para el recorrido único.
Y si C ++ está fuera de la mesa, no hay nada que evite que estos mismos algoritmos se escriban en C.
Una implementación más eficiente
int i, j;
/* new length of modified array */
int NewLength = 1;
for(i=1; i< Length; i++){
for(j=0; j< NewLength ; j++)
{
if(array[i] == array[j])
break;
}
/* if none of the values in index[0..j] of array is not same as array[i],
then copy the current value to corresponding new position in array */
if (j==NewLength )
array[NewLength++] = array[i];
}
En esta implementación no hay necesidad de ordenar la matriz. Además, si se encuentra un elemento duplicado, no es necesario desplazar todos los elementos después de esto en una posición.
El resultado de este código es array [] con tamaño NewLength
Aquí estamos comenzando desde el segundo elemt en array y comparándolo con todos los elementos en el array hasta este array. Estamos manteniendo una variable de índice adicional ''NewLength'' para modificar la matriz de entrada. NewLength variabel se inicializa a 0.
El elemento en la matriz [1] se comparará con la matriz [0]. Si son diferentes, entonces value in array [NewLength] se modificará con array [1] e incrementará NewLength. Si son iguales, NewLength no se modificará.
Entonces, si tenemos una matriz [1 2 1 3 1], entonces
En la primera pasada del bucle ''j'', el conjunto [1] (2) se comparará con el conjunto 0, luego 2 se escribirán en el conjunto [NewLength] = conjunto [1], por lo que el conjunto será [1 2] ya que NewLength = 2
En el segundo paso del bucle ''j'', la matriz [2] (1) se comparará con la matriz 0 y la matriz1. Aquí, dado que la matriz [2] (1) y la matriz 0 son el mismo lazo, se romperán aquí. entonces array será [1 2] ya que NewLength = 2
y así
Una matriz debe obviamente "atravesar" de derecha a izquierda para evitar una copia innecesaria de valores hacia adelante y hacia atrás.
Si tiene memoria ilimitada, puede asignar una matriz de bits para sizeof(type-of-element-in-array) / 8 bytes para que cada bit signifique si ya ha encontrado el valor correspondiente o no.
Si no lo haces, no puedo pensar en nada mejor que atravesar una matriz y comparar cada valor con los valores que lo siguen y luego, si se encuentra el duplicado, elimina estos valores por completo. Esto está cerca de O (n ^ 2) (o O ((n ^ 2-n) / 2) ).
IBM tiene un article sobre un tema cercano.
Una solución sugerida por mi novia es una variación del tipo de fusión. La única modificación es que durante el paso de fusión, simplemente ignore los valores duplicados. Esta solución sería también O (n log n). En este enfoque, la eliminación de clasificación / duplicación se combinan juntas. Sin embargo, no estoy seguro si eso hace alguna diferencia, sin embargo.
Use el filtro de floración para mezclar. Esto reducirá la sobrecarga de la memoria de manera muy significativa.
Veamos:
- O (N) pase para encontrar la asignación mínima / máxima
- matriz de bits para encontrado
- O (N) pase intercambiando duplicados para finalizar.
1. Usando O (1) espacio extra, en el tiempo O (n log n)
Esto es posible, por ejemplo:
- primero haz un ordenamiento en el lugar O (n log n)
- luego repase la lista una vez, escriba la primera instancia de cada vuelta al comienzo de la lista
Creo que la pareja de ejel tiene razón en que la mejor manera de hacer esto sería un tipo de fusión in situ con un paso de fusión simplificado, y esa es probablemente la intención de la pregunta, por ejemplo. escribir una nueva función de biblioteca para hacer esto de la manera más eficiente posible sin posibilidad de mejorar las entradas, y habría casos en los que sería útil hacerlo sin una tabla hash, dependiendo del tipo de entradas. Pero en realidad no he comprobado esto.
2. Usando O (lotes) espacio extra, en el tiempo O (n)
- declarar una matriz de cero lo suficientemente grande como para contener todos los enteros
- caminar a través de la matriz una vez
- establece el elemento de matriz correspondiente en 1 para cada entero.
- Si ya era 1, omita ese entero.
Esto solo funciona si se cumplen varias suposiciones cuestionables:
- es posible cero memoria a bajo costo, o el tamaño de las entradas es pequeño en comparación con el número de ellas
- le complace pedirle a su sistema operativo que tenga 256 ^ sizepof (int) memory
- y lo almacenará en caché para usted realmente realmente eficiente si es gigantesco
Es una mala respuesta, pero si tienes MUCHOS elementos de entrada, pero todos son enteros de 8 bits (o incluso enteros de 16 bits), podría ser la mejor manera.
3. O (pequeño) -espacio extra, O (n) -esa vez
Como # 2, pero usa una tabla hash.
4. La manera clara
Si la cantidad de elementos es pequeña, escribir un algoritmo apropiado no es útil si otro código es más rápido de escribir y más rápido de leer.
P.ej. Recorre la matriz para cada elemento único (es decir, el primer elemento, el segundo elemento (los duplicados del primero han sido eliminados), etc.) eliminando todos los elementos idénticos. O (1) espacio extra, O (n ^ 2) tiempo.
P.ej. Use las funciones de la biblioteca que hacen esto. la eficiencia depende de la que tenga fácilmente disponible.
Given an array of n elements, write an algorithm to remove all duplicates from the array in time O(nlogn)
Algorithm delete_duplicates (a[1....n])
//Remove duplicates from the given array
//input parameters :a[1:n], an array of n elements.
{
temp[1:n]; //an array of n elements.
temp[i]=a[i];for i=1 to n
temp[i].value=a[i]
temp[i].key=i
//based on ''value'' sort the array temp.
//based on ''value'' delete duplicate elements from temp.
//based on ''key'' sort the array temp.//construct an array p using temp.
p[i]=temp[i]value
return p.
In other of elements is maintained in the output array using the ''key''. Consider the key is of length O(n), the time taken for performing sorting on the key and value is O(nlogn). So the time taken to delete all duplicates from the array is O(nlogn).
First, you should create an array check[n] where n is the number of elements of the array you want to make duplicate-free and set the value of every element(of the check array) equal to 1. Using a for loop traverse the array with the duplicates, say its name is arr , and in the for-loop write this :
{
if (check[arr[i]] != 1) {
arr[i] = 0;
}
else {
check[arr[i]] = 0;
}
}
With that, you set every duplicate equal to zero. So the only thing is left to do is to traverse the arr array and print everything it''s not equal to zero. The order stays and it takes linear time (3*n).
this is what i''ve got, though it misplaces the order we can sort in ascending or descending to fix it up.
#include <stdio.h>
int main(void){
int x,n,myvar=0;
printf("Enter a number: /t");
scanf("%d",&n);
int arr[n],changedarr[n];
for(x=0;x<n;x++){
printf("Enter a number for array[%d]: ",x);
scanf("%d",&arr[x]);
}
printf("/nOriginal Number in an array/n");
for(x=0;x<n;x++){
printf("%d/t",arr[x]);
}
int i=0,j=0;
// printf("i/tj/tarr/tchanged/n");
for (int i = 0; i < n; i++)
{
// printf("%d/t%d/t%d/t%d/n",i,j,arr[i],changedarr[i] );
for (int j = 0; j <n; j++)
{
if (i==j)
{
continue;
}
else if(arr[i]==arr[j]){
changedarr[j]=0;
}
else{
changedarr[i]=arr[i];
}
// printf("%d/t%d/t%d/t%d/n",i,j,arr[i],changedarr[i] );
}
myvar+=1;
}
// printf("/n/nmyvar=%d/n",myvar);
int count=0;
printf("/nThe unique items:/n");
for (int i = 0; i < myvar; i++)
{
if(changedarr[i]!=0){
count+=1;
printf("%d/t",changedarr[i]);
}
}
printf("/n");
}
Sería genial si tuvieras una buena estructura de datos que pudiera decir rápidamente si contiene un número entero. Tal vez un árbol de algún tipo.
DataStructure elementsSeen = new DataStructure();
int elementsRemoved = 0;
for(int i=0;i<array.Length;i++){
if(elementsSeen.Contains(array[i])
elementsRemoved++;
else
array[i-elementsRemoved] = array[i];
}
array.Length = array.Length - elementsRemoved;
import java.util.ArrayList;
public class C {
public static void main(String[] args) {
int arr[] = {2,5,5,5,9,11,11,23,34,34,34,45,45};
ArrayList<Integer> arr1 = new ArrayList<Integer>();
for(int i=0;i<arr.length-1;i++){
if(arr[i] == arr[i+1]){
arr[i] = 99999;
}
}
for(int i=0;i<arr.length;i++){
if(arr[i] != 99999){
arr1.add(arr[i]);
}
}
System.out.println(arr1);
}
}