Найти дубликаты между массивами

Question

Предположим, вам даны два массива целых чисел постоянной длины, равной 3, и вы всегда уверены, что два элемента из этих двух массивов будут иметь одинаковые значения.

, поэтому предположим, что массив A имеет три значения: a, b, c. и массив B имеет три значения: d, e, f.

мы уверены, что два значения будут одинаковыми. нас просят поместить эти четыре разных значения в массив размера 4, так что выходной массив C должен иметь в индексах 1 и 2 одинаковые значения из массивов A и B. и в индексах 0 и 3 он должен иметь разные значения массивов A и B. Я реализовал его, но на самом деле не удовлетворен этим решением ... у кого-нибудь есть идея лучшего решения? кроме того, который поместил бы мои счетчики в массив ...:)

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

Извините, я перечитал более внимательно и думаю, что это то, что вы хотите. Пожалуйста, порекомендуйте. :)

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

Вот классное решение на С (++)

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]);

Пример: 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

поэтому c получает значение {1,3,5,2}, как требуется!

Ради интереса, вот версия для компакт-диска:

/* 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]);

Обратите внимание, что достаточно круто, если задача обобщена, так что n-1 элементы являются общими, и в обоих массивах есть один уникальный элемент, это алгоритм O (n), тогда как в общем случае устанавливаются алгоритмы пересечения и / или объединения O (n log n):)

Answer 3

Если у вас есть LINQ, вам будет достаточно следующего кода:

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

Объединение проверяет дубликаты, поэтому дальнейшая проверка не требуется:

Возвращает: An System.Collections.Generic.IEnumerable который содержит элементы из обоих входные последовательности, исключая дубликаты.

Answer 4

То, что вы ищете, это просто набор из двух массивов (набор содержит каждый элемент не более одного раза).Решение в с ++:

#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 5

Заменить

// IRQ. 20100211. Deleted unncessary code

с

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

Обновление:

Новый:

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

или эти

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

Answer 6

Как насчет этого?

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();

    }

Answer 7

Быстрее

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];
    }
}

быстрый

    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 8

Sapph дал такой же чистый ответ, как и он, но вот один, если производительность чрезвычайно важна. Проверка границ массива .NET, вероятно, добавит некоторые издержки, но в C это компилирует до 64 инструкций без ветвей.

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 9

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 10

Вот некоторый простой код, но он предполагает, что значения в a и b всегда положительны.

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];

Я не проверял это, но, надеюсь, вы поняли идею. Это использует очень мало дополнительного пространства (только пространство для notfound, которое можно сделать логическим, и индексные переменные) и должно быть довольно быстрым.