Buscar duplicados entre matrices

Question

Supongamos que tiene dos matrices de enteros de longitud constante que es 3 y siempre está seguro de que dos elementos de la matriz dada tendrán los mismos valores.

asume que la matriz A tiene tres valores: a, b, c. y la matriz B tiene tres valores: d, e, f.

estamos seguros de que dos de los valores serán los mismos. se nos pide que coloquemos estos cuatro valores diferentes en una matriz de tamaño 4, de modo que la matriz de salida C tenga en los índices 1 y 2 los mismos valores de las matrices A y B. y en los índices 0 y 3 debería tener los diferentes valores de la matriz A y B. lo he implementado, pero realmente no estoy satisfecho con esta solución ... ¿alguien tiene una mejor idea de solución? excepto el que pondría mis contadores en serie ... :)

int[] a = { 1, 201, 354 }; 
int[] b = { 404, 201, 354 }; 

int[] c = new int[4]; 

for (int i = 0; i < c.Length; i++) 
{ 
    Console.WriteLine(c[i]); 
} 

Answer 1

Disculpa, vuelvo a leer más y creo que esto es lo que quieres. Por favor avise. :)

int[] same = a.Intersect(b).ToArray(); ; 
int[] diff = a.Union(b).Except(same).ToArray(); 
int[] c = new int[] { diff[0], same[0], same[1], diff[1] }; 

Answer 2

Esta parte

if (a[0] == b[0]) { counter0++; } 
    if (a[0] == b[1]) { counter0++; } 
    if (a[0] == b[2]) { counter0++; } 

    if (a[1] == b[0]) { counter1++; } 
    if (a[1] == b[1]) { counter1++; } 
    if (a[1] == b[2]) { counter1++; } 

    if (a[2] == b[0]) { counter2++; } 
    if (a[2] == b[1]) { counter2++; } 
    if (a[2] == b[2]) { counter2++; } 

probablemente podría reescribirse como

for (i=0; i<3; i++) 
{ 
    for (j=0; j<3; j++) 
    { 
     switch(i) 
     { 
       case 0: 
       if (a[i] == b[j]) { counter0++; } 
       break; 
       case 1: 
       if (a[i] == b[j]) { counter1++; } 
       break; 
       case 2: 
       if (a[i] == b[j]) { counter2++; } 
       break; 
      } 
    } 
} 

La otra parte con los otros contadores debe escribirse de manera similar. Entonces quizás podría refactorizar esto en un método separado y simplemente pasarle las matrices y los contadores.

Otra opción podría ser LINQ, pero no estoy seguro exactamente cómo escribir algo como esto.

(no he probado la compilación de esto, pero es la idea clara?)

ACTUALIZACIÓN: Si usted podría poner los contadores en una matriz, esto podría funcionar:

for (i=0; i<3; i++) 
{ 
    for (j=0; j<3; j++) 
    { 
     if (a[i] == b[j]) { counters[i]++; } 

    } 
} 

Answer 3

I Estoy bastante seguro de que no entiendo la pregunta.

Usted dice:

estamos seguros de que dos de los valores será el mismo. se nos pide que poner estos cuatro valores diferentes

Qué cuatro valores diferentes se refiere? Los dos que son lo mismo? Porque a eso se refiere la palabra "estos".

¿Quiere decir: tomar los 4 valores únicos y ponerlos en una matriz?

Así que:

1, 2, 3
2, 3, 4

se convierte en:

1, 2, 3, 4?

Eso es fácil:

int[] c = a.Concat(b).Distinct().ToArray(); 

Este utiliza los métodos de extensión LINQ de .NET 3.5. Si no estás en .NET 3.5, se puede hacer esto:

Dictionary<int, int> c1 = new Dictionary<int, int>(); 
foreach (var x in a) 
    c1[x] = 1; 
foreach (var x in b) 
    c1[x] = 1; 
int[] c = new List<int>(c1.Keys).ToArray(); 

Ahora, si usted necesita el fin de ser la siguiente:

1. El primer valor que sólo ocurrió una vez
2. El primer valor que se produjo dos veces
3. El segundo valor que se produjo dos veces
4. El segundo valor que sólo se produjo una vez

Entonces me temo que no tengo un trazador de líneas para usted, tendrá que pensarlo un poco más.

¿Puedo preguntar cuál es el contexto? ¿Por qué este requisito?

Answer 4

bool isUsed[6]={true, true, true, true, true, true}; 

int values[6]; 

int valuesCount = 0; 

int i,j; 

for(i = 0 ; i < 3 ; i++) 
{ 
    bool goodValue = true; 
    for (j = 0; j < valuesCount; j++) 
    { 
     if(values[j] == a[i]) 
     { 
      isUsed[j] = false; 
      goodValue = false; 
      break; 
     } 
    } 
    if(goodValue) 
    { 
     values[valuesCount++]=a[i]; 
    } 
} 

//same for b[i] 

for(i = 0 ; i < valuesCount; i++) 
{ 
    if(isUsed[i]) printf("%i ", values[i]); 
} 

Answer 5

En lugar de Counter1 Counter2, counter3:

counter[3]; 

Muchas cosas se ponen más fácil a partir de ahí. Puede referirse a todo en bucles, para empezar.

Answer 6

Se me ocurrió esto como un primer borrador, pero creo que puede necesitar alguna mejora. Tampoco cumple el requisito de tener los duplicados en la posición 1 y 2 y los números únicos en 0 y 3 en la matriz. Yo pensé que había puesto todos modos, para que pueda obtener una idea de cómo esto puede verse como:

int[] a = { 1, 201, 354 }; 
    int[] b = { 404, 201, 354 }; 

    int[] c = new int[ 4 ]; 

    // Start by just copying over one of the arrays completely. 
    a.CopyTo(c, 0); 

    // Loop through b and compare each number against each 
    // each number in a. 
    foreach(int i in b) 
    { 
    // Assume that you're not dealing with a duplicate 
    bool found = true; 
    foreach(int j in a) 
    { 
     // If you find a duplicate, set found to false 
     if(i == j) 
     { 
     found = false; 
     }   
    } 
    // If you haven't found a duplicate this is the 
    // number you want - add it to the array. 
    if (found == true) 
    { 
     c[3] = i; 
    } 
    } 

Answer 7

Reemplazar

// IRQ. 20100211. Deleted unncessary code 

con

var c = a.Concat(b).Distinct().ToArray(); 

Actualización:

Nuevo uno:

var same = a.Intersect(b); 
var c = a.Except(same).Concat(same).Concat(b.Except(same)).ToArray(); 

o estos

var c = a.Except(b).Concat(a.Intersect(b)).Concat(b.Except(a)); 
var c = a.Except(b).Concat(a).Concat(b).Distinct(); 

Answer 8

Lo que se busca es sólo un conjunto de los dos conjuntos (set contiene todos los elementos una vez como máximo). La solución en C++:

#include <set> 

int main() { 
    int a[] = { 1,2,3 }; 
    int b[] = { 4,2,3 }; 

    std::set<int> s(a, a+3); 
    s.insert(b, b+3); 
} 

Answer 9

Estoy tratando de dar una respuesta corta. Sin embargo, asume que la entrada será correcta.

int c1, c2, i; 
c1 = a[0] == b[0] ? 0 
        : (a[0] == b[1] ? 1 : 2); // index of a[0] in array 'b' 
c2 = a[1] == b[0] ? 0 
        : (a[1] == b[1] ? 1 : 2); // index of a[1] in array 'b' 

for(i=0; i<2; i++) 
    Console.WriteLine(a[i]); 
Console.WriteLine(b[3-c1-c2]); // looks quite hacky but it is actually element of 'b' not in array 'a' 

Answer 10

Si tiene LINQ a su disposición, el siguiente código será suficiente:

int[] c = a.Union(b).ToArray(); 

cheques Unión para duplicados, así que sin más comprobación es necesario:

Devuelve: Un System.Collections.Generic.IEnumerable que contiene los elementos de ambas secuencias de entrada , excluidos los duplicados.

Answer 11

Aquí hay un código simple, pero asume que los valores en ayb son siempre positivos.

int[] a = { 1, 201, 354 }; 
int[] b = { 404, 201, 354 }; 

int[] c = { -1, -1, -1, -1}; 

for(int i = 0; i < 3; i++){ 
    int notfound = 1; 
    for(int j = 0; j < 3; j++){ 
     if(b[j] == -1) continue; 

     if(a[i] == b[j]){ 
      b[j] = -1; 
      if(c[1] == -1) 
       c[1] = a[i]; 
      else 
       c[2] = a[i]; 
      notfound = 0; 
      break; 
     } 
    } 
    if(notfound) 
     c[0] = a[i]; 
} 
int k = 0; 
while(b[k++] == -1); 
c[3] = b[k]; 

No lo he probado, pero espero que entiendas la idea. Esto utiliza muy poco espacio extra (solo el espacio para no encontrado, que podría convertirse en booleano, y las variables de índice) y debería ser bastante rápido.

Answer 12

int[] a = { 204, 534, 1 }; 
int[] b = { 204, 534, 401 }; 
int[] c = new int[4]; 

int x = 3, y = 3, k = 1; 
for(int i=0; i<3; i++) 
    for(int j=0; j<3; j++) 
     if (a[i] == b[j]) { 
      c[k++] = a[i]; 
      x -= i; 
      y -= j; 
      break; 
     } 
c[0] = a[x]; 
c[3] = b[y]; 

Answer 13

Aquí una solución fresca en C (++)

int a[3], b[3]; /* the two arrays */ 
int c[4]; /* target */ 
int s=0, t=0, k; 
int i; 
for (i=0;i<3;i++) { k = a[i]-b[i]; s += k; t += k*(a[i]+b[i]); } 

/* At this point s is the difference of the two distinct elements 
    and t is the difference of their squares, i.e. s = x - y and t = x^2 - y^2 
    because (x-y)(x+y) = x^2-yx+yx-y^2 = x^2-y^2 
    Because the two elements are distinct, s != 0 and we can easily divide t 
    by s to get (x + y), from which then we have 
    s == x - y 
    t == x + y 
    i.e. x = (s+t)/2 and y=(t-s)/2 */ 

t /= s; 
int x = (s + t)/2; 
int y = (t - s)/2; 

/* Now x, y are the distinct elements, x from array a and y from array b */ 
/* Fill in the results */ 
c[0] = x; 
c[3] = y; 
/* If a[0] is non-shared, then a[1] must be the first shared element; otherwise a[0] */ 
c[1] = (a[0] == x ? a[1] : a[0]); 
/* If a[2] is non-shared, then a[1] must be the last shared element; otherwise a[2] */ 
c[2] = (a[2] == x ? a[1] : a[2]); 

Ejemplo: a = {1, 3, 5}, b = {3, 5, 2}

s = (1-3)+(3-5)+(5-2) = -2-2+3 = -1 
t = (1-3)*(1+3)+(3-5)*(3+5)+(5-2)*(5+2) = -8-16+21 = -3 
t/s = 3 
x = (-1 + 3)/2 = 1 
y = (3 - (-1))/2 = 2 
c[0] = 1 
c[3] = 2 
c[1] = 3 
c[2] = 5 

por lo que c obtiene el valor {1,3,5,2}, como lo desee.

Para la diversión, aquí una versión más compacta:

/* Declarations */ 
int a[3], b[3], c[4]; 
int s = 0, t = 0, k, i; 

/* Actual algorithm */ 
for (i = 0; i < 3; i++) { s += (k = a[i]-b[i]); t += k * (a[i]+b[i]); } 
t /= s; 
c[0] = (s + t) >> 1; 
c[3] = (t - s) >> 1; 
c[1] = (a[0] == x ? a[1] : a[0]); 
c[2] = (a[2] == x ? a[1] : a[2]); 

Tenga en cuenta que con frialdad suficiente si el problema se generaliza de manera que los elementos de n-1 son compartidos y hay un elemento único en ambas matrices, esto es una junta (n) Algoritmo, mientras que los algoritmos basados ​​en intersección y/o unión en general son O (n log n) :)

Answer 14

Sapph proporcionó una respuesta que es casi tan clara como se puede, pero aquí hay una si el rendimiento es extremadamente importante. La comprobación de límites de la matriz .NET probablemente agregará algo de sobrecarga, pero en C esto compila hasta 64 instrucciones sin ramificaciones.

int[] a = { 204, 534, 1 }; 
int[] b = { 204, 534, 401 }; 
int[] c = new int[4]; 

// pick the value from a that is not in b for c[0] 
// a[0] not in b is implied by a[1] in b and a[2] in b 
int a1_not_in_b = Convert.ToInt32(a[1] != b[0] & a[1] != b[1] & a[1] != b[2]); 
int a2_not_in_b = Convert.ToInt32(a[2] != b[0] & a[2] != b[1] & a[2] != b[2]); 

// bitfield of 2 bit values equivalent to the array {0,1,2,0,1} 
int idxs = 0 | 1 << 2 | 2 << 4 | 0 << 6 | 1 << 8; 
// if a[1] not in b start at 1, if a[2] not in b start at 2, else start at 0 
idxs >>= 2*a1_not_in_b | 4*a2_not_in_b; 
c[0] = a[(idxs >> 0) & 3]; 
c[1] = a[(idxs >> 2) & 3]; 
c[2] = a[(idxs >> 4) & 3]; 

// pick the value from b that is not in a 
// b[0] not in a is implied by b[1] in a and b[2] in a 
int b1_not_in_a = Convert.ToInt32(a[0] != b[1] & a[1] != b[1] & a[2] != b[1]); 
int b2_not_in_a = Convert.ToInt32(a[0] != b[2] & a[1] != b[2] & a[2] != b[2]); 
c[3] = b[b1_not_in_a | 2*b2_not_in_a]; 

Answer 15

¿Más rápido?

using System; 
using System.Linq; 
using sw = System.Diagnostics.Stopwatch; 
class Program 
{ 
    static void Main() 
    { 
     int[] a = new int[] { 1, 2, 3 }, // try: a={1,2,2} b={2,2,3} 
       b = new int[] { 4, 2, 3 }, c = new int[4]; 
     sw sw = sw.StartNew(); 
     for (int i = 5000000; i > 0; i--) { dssd1(a, b, c); dssd1(b, a, c); } 
     Console.Write(sw.ElapsedMilliseconds); 
     Console.Read(); 
    } 

    static void dssd0(int[] a, int[] b, int[] c)    // 6710 ms. 
    { 
     int[] s = a.Intersect(b).ToArray();  // same 
     int[] d = a.Union(b).Except(s).ToArray(); // diff 
     c[0] = d[0]; c[1] = s[0]; c[2] = s[1]; c[3] = d[1]; 
    } 

    static void dssd1(int[] a, int[] b, int[] c)    // 61 ms. 
    { 
     if (a[0] != b[0] && a[0] != b[1] && a[0] != b[2]) 
     { c[0] = a[0]; c[1] = a[1]; c[2] = a[2]; goto L0; } 
     if (a[1] != b[0] && a[1] != b[1] && a[1] != b[2]) 
     { c[0] = a[1]; c[1] = a[0]; c[2] = a[2]; goto L0; } 
     c[0] = a[2]; c[1] = a[0]; c[2] = a[1]; 
    L0: if (b[0] != c[1] && b[0] != c[2]) { c[3] = b[0]; return; } 
     if (b[1] != c[1] && b[1] != c[2]) { c[3] = b[1]; return; } 
     c[3] = b[2]; 
    } 
} 

¿Más rápido?

L0: c[3] = b[0] != c[1] && b[0] != c[2] ? b[0] :   // 49 ms. 
     b[1] != c[1] && b[1] != c[2] ? b[1] : b[2]; 

Answer 16

¿Qué tal esto?

private static int[] FindDuplicates(int[] arrA,int[] arrB) 
    { 
     var aList=new List<int>(); 
     Array.Sort(arrA); 
     Array.Sort(arrB); 


     for(int i=0;i<arrA.Length;i++) 
     { 
      if(arrB.Contains(arrA[i])) 
      {   
      aList.Add(arrA[i]); 
      } 

     } 
     return aList.ToArray(); 

    }