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

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

Я пытаюсь дать краткий ответ. Однако предполагается, что ввод будет правильным.

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'

Эта часть

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

Возможно, может быть переписана как

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

Другая часть с другими счетчиками должна быть написано аналогично. Затем вы могли бы преобразовать это в отдельный метод и просто передать ему массивы и счетчики.

Другим вариантом может быть LINQ, но я не совсем уверен, как написать что-то подобное.

(Не пробовал скомпилировать это, но ясна ли идея?)

ОБНОВЛЕНИЕ: Если бы вы могли поместить счетчики в массив, это могло бы сработать:

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

     }
}

Я уверен, что не понимаю вопроса.

Вы говорите:

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

На какие четыре разных значения вы ссылаетесь? Те два, которые одинаковы? Потому что так называется слово «эти».

Вы имеете в виду: Взять 4 уникальные значения и поместить их в массив?

Так что:

1, 2, 3
2, 3, 4

Становится:

1, 2, 3, 4?

Это просто:

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

Используются методы расширения Linq для .NET 3,5. Если вы не находитесь на .NET 3.5, вы можете сделать это:

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

Теперь, если вам нужно, чтобы порядок был таким:

1. Первое значение, которое произошло только один раз
2. Первое значение, которое произошло дважды
3. Второе значение, которое произошло дважды
4. Второе значение, которое произошло только один раз

Тогда я боюсь, что у меня нет одного

Могу ли я спросить, каков контекст? Почему это требование?

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

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

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

Я придумал это в качестве первого проекта, но я думаю, что он нуждается в улучшении. Он также не удовлетворяет требованию о наличии дубликатов в позиции 1 и 2 и уникальных номеров в 0 и 3 в массиве. Я подумал, что все равно опубликую его, чтобы вы могли получить представление о том, как это может выглядеть:

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

Это, согласно документации

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

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

Если это будет особенно большой список, и у вас есть довольно хорошее представление о размере, это не повредит. Тем не менее, если оценка размера включает в себя дополнительные вычисления или какой-либо значительный объем кода, я не буду беспокоиться об этом, если вы не обнаружите, что это станет проблемой - это может отвлечь внимание от основного фокуса кода, и изменение размера вряд ли вызовет проблемы с производительностью, если это действительно большой список или вы делаете это много.

Я почти уверен, что не понимаю вопрос.

Вы говорите:

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

На какие четыре разных значения вы ссылаетесь? Те два, которые одинаковы? Потому что так называется слово «эти».

Вы имеете в виду: Взять 4 уникальные значения и поместить их в массив?

Так что:

1, 2, 3
2, 3, 4

Становится:

1, 2, 3, 4?

Это просто:

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

Используются методы расширения Linq для .NET 3,5. Если вы не находитесь на .NET 3.5, вы можете сделать это:

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

Теперь, если вам нужно, чтобы порядок был таким:

1. Первое значение, которое произошло только один раз
2. Первое значение, которое произошло дважды
3. Второе значение, которое произошло дважды
4. Второе значение, которое произошло только один раз

Тогда я боюсь, что у меня нет одного

Могу ли я спросить, каков контекст? Почему это требование?

Вместо counter1, counter2, counter3:

counter[3];

Многие вещи становятся проще. Для начала вы можете ссылаться на все в циклах.

Если в вашем распоряжении LINQ, будет достаточно следующего кода:

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

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

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

Замените

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

То, что вы ищете, - это просто набор из двух массивов (набор содержит каждый элемент не более одного раза). Решение на 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);
}

Как это?

var Cat = Function (a, b, c, d, e, f, g, h, i, j, k , l, m, n){
   Animal.apply(this, arguments);
};

// inherit functions if any
Cat.prototype = new Animal;

var y = new Cat(1,2,3....);

Вам, безусловно, нужно будет перекомпилировать файлы байт-кода, чтобы они могли использоваться. Магическое число байт-кода изменилось в каждой основной версии Python (*).

Однако наличие файлов байт-кодов, не соответствующих версии, не должно приводить к аварийному завершению работы Python. Обычно он просто игнорирует любой байт-код, который не имеет правильного номера версии, поэтому не должно быть ошибки, он будет просто медленнее в первый раз, когда он перекомпилирует (или медленнее каждый раз, если пользователь, выполняющий сценарии, не имеет разрешения на запись для обновления байт-кода).

(*: и часто на этапах разработки, плюс в более ранних версиях он иногда менялся и на второстепенные версии. Полный список магических чисел и соответствующих им версий Python см. в import.c .)

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

Вот простой код, но он предполагает, что значения в 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, который можно сделать булевым, и индексные переменные) и должно быть довольно быстро.

Вот классное решение на 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]);

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