una - eliminar valores repetidos en un array c#

Encuentre duplicados en una matriz con un enfoque de memoria eficiente

Question

A es una matriz de enteros.

Todos los valores están entre 0 a A.Length-1

significa 0 <= A[i] <= A.Length-1

Se supone que debo encontrar elementos que se repiten; y si hay varios elementos que se repiten, elija el que tenga menor índice para el elemento repetido.

por ejemplo:

a = [3, 4, 2, 5, 2, 3]

entonces

result = 2

Esta fue una pregunta de entrevista. Utilicé otra matriz para almacenar artículos y verificar cuándo se está repitiendo. Luego me dio tiempo de espera para algunos casos de prueba. El entrevistador aconsejó que solo pasara sobre la matriz solo una vez y no creara ninguna estructura de datos adicional.

Answer 1

Me gustaría refinar la solución de @ AryanFirouzian y devolver todos los duplicados utilizando el yield return . Además, el uso de una variable temporal simplifica el código.

public static IEnumerable<int> FindDuplicates(int[] A)
{
    for (int i = 0; i < A.Length; i++) {
        int absAi = Math.Abs(A[i]);
        if (A[absAi] < 0) {
            yield return absAi;
        } else {
            A[absAi] *= -1;
        }
    }
}

Sin embargo, esta solución no devuelve el elemento con el índice inferior y, si hay más de 2 copias idénticas, devolverá el mismo valor más de una vez. Otro problema es que 0 no puede hacerse negativo.

Una mejor solución elimina los resultados repetidos, pero aún así devuelve el segundo índice y tiene un problema con 0 valores. También devuelve el índice para demostrar el problema del índice incorrecto

public static IEnumerable<(int index, int value)> FindDuplicates(int[] A)
{
    for (int i = 0; i < A.Length; i++) {
        int x = A[i] % A.Length;
        if (A[x] / A.Length == 1) {
            yield return (i, x);
        }
        A[x] += A.Length;
    }
}

Probado con

var A = new int[] { 3, 4, 2, 5, 2, 3, 3 };
foreach (var item in FindDuplicates(A)) {
    Console.WriteLine($"[{item.index}] = {item.value}");
}

Vuelve

[4] = 2
[5] = 3

Mi solución final que elimina todos estos problemas (al menos eso espero): Codifica el primer índice en sí al agregar (i + 1) * A.Length a la primera aparición de un valor. (i + 1) porque puedo ser 0 . El índice se puede decodificar con la operación inversa (A[x] / A.Length) - 1 .

Luego, debido a que queremos devolver un resultado solo en el primer valor de repetición, establecemos el valor en un valor negativo para excluirlo de un procesamiento posterior. Posteriormente, el valor original se puede recuperar con Math.Abs(A[i]) % A.Length .

public static IEnumerable<(int index, int value)> FindDuplicates(int[] A)
{
    for (int i = 0; i < A.Length; i++) {
        int x = Math.Abs(A[i]) % A.Length;
        if (A[x] >= 0) {
            if (A[x] < A.Length) { // First occurrence.
                A[x] += (i + 1) * A.Length; // Encode the first index.
            } else { // Second occurrence.
                int firstIndex = (A[x] / A.Length) - 1; // Decode the first index.
                yield return (firstIndex, x);

                // Mark the value as handeled by making it negative;
                A[x] *= -1; // A[x] is always >= A.Length, so no zero problem.
            }
        }
    }
}

Devuelve el resultado esperado.

[2] = 2
[0] = 3

Nuestros elementos son intactos que no tienen identidad. Es decir, podemos devolver uno de los duplicados en cualquier índice ya que no se pueden distinguir dos ints iguales. En caso de que los elementos tengan una identidad (podrían ser tipos de referencia con valores iguales pero referencias diferentes o tener campos adicionales que no participan en las pruebas de igualdad), tendríamos que devolver la primera aparición con

yield return (firstIndex, Math.Abs(A[firstIndex]) % A.Length);

Para satisfacer todos los requisitos.

Answer 2

No hay necesidad de otra estructura de datos. Puede utilizar la entrada en sí como un hashset.

Cada vez que vea un valor, agregue A.Length al elemento que corresponde a ese índice. Como es posible que los valores ya se hayan incrementado, debe ver el valor como A[i] mod A.length .

Si encuentra un elemento que ya es> = A.longitud ... tiene una repetición. (Recuerde que el problema indica que todos los elementos están en el intervalo [0, A.Length-1] )

Seguimiento del índice más bajo que se ha encontrado como repetido.

Esto da como resultado una complejidad O (N) (pase único) y no se utiliza una estructura de datos adicional, es decir, tamaño O (1)

El concepto clave detrás de este enfoque es que los hashsets funcionan de esta manera. Conceptualmente, esto se relaciona indirectamente con el principio del casillero. https://en.wikipedia.org/wiki/Pigeonhole_principle

Nota: Durante la entrevista, sería importante hacer preguntas específicas de implementación, discutir limitaciones, suposiciones, etc.: ¿Cuál es el tipo de datos de los elementos en la lista? - si los valores están en el rango [0..A.length-1], ¿todos los elementos están sin firmar o puedo usar números negativos si quisiera? - etc.

Durante la entrevista, no diría que esta es una respuesta perfecta; en cambio, discutiría las suposiciones con el entrevistador y las ajustaría en consecuencia. Por ejemplo, otra respuesta sugiere el uso de números negativos, pero es posible que el tipo de datos de los elementos sea un tipo sin signo, etc.

Se supone que la entrevista provocará una discusión técnica para explorar tanto su conocimiento como su creatividad.

Answer 3

Para quien quiera una implementación del problema, sugiero dos variantes (en c # como en las etiquetas), una con la respuesta aceptada y otra con el enfoque de otra respuesta, utilizando el opuesto de los elementos. Sin embargo, la última solución tiene un problema con el valor cero y requiere algún truco.

Primera solucion

using System;
public class Program
{
    public static void Main()
    {
        int[] a = {3, 4, 0, 5, 2, 3};
        int N = 6;
        int min_index = 0; 
        bool found = false;
        int index = -1;
        int i = 0;
        while(i < N && !found)
        {

            if(a[i] >= N) 
                index = a[i] % N;
            else
                index = a[i];

            if(a[index] >= N) //its a duplicated elements 
            {
                min_index = i;
                found = true;
            }else
            {
                a[index] += N;
            }
            i++;

        }

        Console.WriteLine("Result = " + a[min_index] % N);
    }
}

Segunda solucion

    using System;
public class Program
{
    public static void Main()
    {
        int[] a = {3, 4, 2, 5, 2, 3};
        int N = 6;
        int min_index = N-1; 
        bool found = false;
        int index = -1;
        int i = 0;
        while(i < N && !found)
        {
            if(a[i] == -N+1) //it was 0
                index = 0;
            else
                index = Math.Abs(a[i]);

            if(a[index] < 0 || a[index] == -N+1) //its a duplicated elements 
            {
                min_index = i;
                found = true;
            }else
            {
                if(a[index] > 0)
                {
                    a[index] = -a[index];
                }else
                {
                    a[index] += -N+1;
                }
            }
            i++;
        }

        if(a[min_index] == -N+1)
            a[min_index] = 0;

        Console.WriteLine("Result = " + Math.Abs(a[min_index]));
    }
}

Answer 4

Aviso: la solución falla si hay un elemento con valor de cero. La solución de Olivier puede manejar tales casos.

Haciendo elemento con índice de A [i] negativo. Solo pasa por el bucle una vez.

for(int i=0; i<A.Length; i++)
    {
        if (A[Math.Abs(A[i])] < 0){ return Math.Abs(A[i]);}
        A[Math.Abs(A[i])] = -A[Math.Abs(A[i])];
    }