Различение дополнительного элемента от двух массивов?

Невозможно решить эту проблему без сравнений. В некоторых современных языках есть установочные операторы различия и другие агрегатные операторы, но они работают путем внутреннего сравнения. Если общий размер массива нечетный (в данном случае это не так), то он работает для xor элементов вместе. Я полагаю, что вопрос о том, следует ли рассматривать операцию ALU xor как сравнение, является спорным.

И без указания языка вы не можете ссылаться на библиотеку, поэтому единственное возможное решение - это сравнение описание псевдокода на основе.

Итак, пожалуйста:

a <- first element
a_count = 1
b_count = 0
loop over remaining elements
   if element != a
     b <- element
     ++b_count
   else
     ++a_count
   if found_result
      break loop
end loop

found_result
   if a_count > 1 and b_count > 0
     the unique one is b
     return true
   if b_count > 1 and a_count > 0 # a_acount actually always > 0
     the unique one is a
     return true
   return false

В зависимости от языка, который вы используете, он может иметь встроенный способ обработки различий в массивах. PHP поддерживает http://ca3.php.net/array_diff

Вот еще одна возможность. В отличие от моего предыдущего ответа он не изменяет переданные массивы и должен иметь нижнюю границу большого O (O (n) вместо O (n ^ 2) - при условии постоянного поиска по хеш-таблице), но будет занимать значительно больше памяти.

function findUnique(a:Array, b:Array):Array {
  var aHash:Hashtable = buildHash(a);
  var bHash:Hashtable = buildHash(b);

  var uniqueFromA:int;
  var uniqueFromB:int;

  for each(value:int in a) {
    if(!bHash.contains(value)) {
      uniqueFromA = value;
      break;
    } else {
      /* Not necessary, but will speed up the 2nd for-loop by removing
       * values we know are duplicates. */
      bHash.remove(value);
    }
  }

  for each(value:int in b) {
    if(!aHash.contains(value)) {
      uniqueFromB = value;
      break;
    }
  }

  return [uniqueFromA, uniqueFromB];
}

function buildHash(a:Array):Hashtable {
  var h:Hashtable = new Hashtable();
  for each(value:int in a) {
    h[value] = true;
  }

  return h;
}

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

Вот решение для линейного времени.

Во-первых, мы должны построить хэш на основе одного массива. Поиск значений в хеш-таблице требует O (1 + k / n) сравнений [1], где k - длина хеш-таблицы. Таким образом, итерация по первому массиву (который содержит n элементов) и поиск каждого значения занимает O (n + k).

Затем мы перебираем другой массив, ища каждый элемент в хэше. Когда элемент не найден - это уникальный элемент из другого массива. (Снова O (n + k)). Затем мы перебираем хеш-код для поиска второго уникального элемента (O (k)).

Общее время O (n + k). Поскольку это не t имеет смысл позволить k быть больше n, это линейное решение.

Perl-код для этого:

sub unique
{
  my ($arr, $brr) = @_;
  my %hash = map{$_ => 1} @$arr;
  %hash{$_}-- for @$brr;
  return grep {$_} keys %hash;
}

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

function findUnique(a:Array, b:Array):Array {
  var uniqueFromA:int;
  var uniqueFromB:int;

  for each(value:int in a) {
    var len:int = b.length;
    b.remove(value);
    /* b's length didn't change, so nothing was removed, so the value doesn't
     * exist in it. */
    if(b.length == len) {
      uniqueFromA = value;
    }
  }

  /* Only the unique value in b still exists in b */
  uniqueFromB = b[0];

  return [uniqueFromA, uniqueFromB];
}

• Вы указали два целочисленных массива, каждый размером 10.
• Оба содержат 9 одинаковых элементов (скажем, от 1 до 9)
• Только один элемент отличается.

В зависимости от типа ограничения, вы можете решить эту проблему очень быстро за линейное время. Если у вас есть int [10], то вы можете предположить, что элемент с индексом 1 соответствует номеру 1; сам элемент содержит количество обоих массивов. Следующий псевдокод быстро решит проблему:

let buckets = new int[10] // init all buckets to zero
for num in arr1 do buckets[num]++ // add numbers from the first array
for num in arr2 do buckets[num]++ // add from the second array
for i in 1 to 9 do                // find odd man out
    if buckets[i] <= 1 then return i

По сути, это ограниченная хеш-таблица. Это работает только , если наш список элементов ограничен от 1 до 9.

Технически вам даже не нужно вести текущий счетчик каждого элемента. В принципе, вы могли бы просто пройти через arr1, а затем пройти через arr2 до тех пор, пока не встретите элемент, который не был хеширован из первого массива.

Вот математический подход, вдохновленный ответом Кевина и его комментариями.

Давайте назовем массивы A и B и позволим их уникальным элементы будут a и b соответственно. Сначала возьмите суммы обоих массивов и вычтите один из другого; так как все остальное сокращается, sum (A) - sum (B) = a - b = s . Затем умножьте элементы обоих массивов и разделите один на другой. Опять же, все отменяется, поэтому mult (A) / mult (B) = a / b = r . Теперь из них получаем a = rb , поэтому rb - b = s или b = s / (r - 1) , а затем a = rs / (r - 1) .

Я называю это математическим, потому что умножение значений может быть неразумным занятием в реальной программе. Ключ состоит в том, чтобы иметь две разные операции, каждая из которых индивидуально допускает отмену поведения и так, чтобы одна распределялась по другой. Это последнее свойство используется при переходе от rb - b = s к b = s / (r - 1) , и это не будет работать, скажем, с добавлением и XOR, это была моя первая попытка.

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

Простая версия в Ruby

def unique(a,b)
  h={}
  a.each do |ax|
    h[ax]=true
  end
  b.each do |bx|
    if h[bx]
      h.delete(bx)
    else
      h[bx]=true
    end
  end
  h.keys
end

С немного большей индивидуальностью Ruby, но все же во вселенной, где мы не можем просто сделать ( a | b) - (a & b) или a.to_set ^ b.to_set :

def unique(a,b)
  h = {}
  a.each do |ax|
    h[ax] = true
  end
  b.each do |bx|
    h.delete(bx) or h[bx] = true
  end
  h.keys
end

In LINQ:

var unique1 = (from a in arrayA where !arrayB.Contains(a) select a).First();
var unique2 = (from b in arrayB where !arrayA.Contains(b) select b).First();
return new Pair(unique1, unique2);

...

public sealed class Pair<T0, T1>
{
    public T0 Item1 {get;set;}
    public T1 Item2 {get;set;}
    public Pair(T0 item1, T1 item2)
    {
        Item1 = item1;
        Item2 = item2;
    }
    //plus GetHashCode, equality etc.
}

This can be solved quickly from just the sum and the sum of the squares of the two sequences. And calculating these sums will certainly be faster than the hashes that are suggested, and doesn't involve any comparisons between the sequence items.

Here's how to do it: If the two sets are {a_i} and {b_i}, then call A and B their sums, and A2 and B2 are the sum of the squares, i.e. A2 = Sum({a_i²}), and for convenience, D=A-B, and D2=A2-B2. Therefore, D=a-b and D2=a²-b², where a and b are the two elements that are different, and from this we see

a = (D²+D2)/(2*D)
b = a - D

This works out because, from algebra, a²-b²=(a+b)(a-b) or D2=(a+b)D, so a+b=D2/D, and since we also know a-b, we can find a and b.

An example in Python may be more convincing

a, b = 5, 22   # the initial unmatched terms
x, y = range(15), range(15)
y[a] = b
print "x =", x  # x = [0, 1, 2, 3, 4,  5, 6, 7, 8, 9, 10, 11, 12, 13, 14]
print "y =", y  # y = [0, 1, 2, 3, 4, 22, 6, 7, 8, 9, 10, 11, 12, 13, 14]

D = sum(x) - sum(y)
D2 = sum([i**2 for i in x]) - sum([i**2 for i in y])  #element-wise squaring
a = (D2+D*D)/(2*D)
b = a - D

print "a=%i, b=%i" % (a, b)
#prints a=5, b=22  which is correct

(Of course, this is somewhat similar to jk's answer, except it doesn't require the multiplication of all the terms and the huge numbers that would result, but thanks to jk for the idea of a mathematical approach.)

Логика, лежащая в основе почти всех предыдущих ответов, всегда одна и та же: используйте математические операции над множеством для решения задачи.

Математический набор может содержать каждый элемент только один раз. Таким образом, следующий список не может быть набором в математическом смысле, поскольку он содержит одно число (3) дважды:

{ 1, 2, 3, 4, 3, 5 }

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

// Construct set from first list:
Set uniques = Set.from(list1);

// Iterate over second list, check each item’s existence in set.
for each (item in list2)
    if (not uniques.Contains(item))
        return item;

Различные реализации наборов дают разную производительность, но эта производительность всегда будет выше, чем у наивного решения (для больших списков). В частности, существуют две реализации:

• В виде (самосбалансированного) дерева поиска . В дереве элементы отсортированы, поэтому поиск конкретного элемента эффективен с помощью двоичного поиска (или его варианта). Таким образом, поиск имеет производительность O (log n ). Создание набора деревьев из входных данных имеет производительность O ( n · log n ). Это также и общая производительность.
• Хеш-таблицы могут быть реализованы так, чтобы иметь производительность поиска в среднем случае O (1) (и с помощью нескольких уловок это также может быть сделано для наихудшей производительности) . Создание хеш-таблицы может быть выполнено за O ( n ). Следовательно, хеш-таблицы могут достичь общего времени выполнения O ( n ).
• Фильтры Блума предлагают хорошее вероятностное решение - то есть решение может на самом деле быть неправильным, но мы можем контролировать, насколько (не) вероятно это будет. Это особенно интересно, потому что это очень компактно.
• … существует много других реализаций.

В каждом случае использование остается прежним, а приведенный выше псевдокод дает справочное решение вашей проблемы. Реализация Java может выглядеть следующим образом:

// Construct set from first list:
Set<Integer> uniques = new HashSet<Integer>(list1);

// Iterate over second list, check each item’s existence in set.
for (int item : list2)
    if (! uniques.Contains(item))
        return item;

Обратите внимание, как это выглядит почти так же, как псевдокод. Решения на C #, C ++ или других языках не сильно отличаются.

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

использование остается прежним, и приведенный выше псевдокод дает учебное решение вашей проблемы. Реализация Java может выглядеть следующим образом:

// Construct set from first list:
Set<Integer> uniques = new HashSet<Integer>(list1);

// Iterate over second list, check each item’s existence in set.
for (int item : list2)
    if (! uniques.Contains(item))
        return item;

Обратите внимание, как это выглядит почти так же, как псевдокод. Решения на C #, C ++ или других языках не сильно отличаются.

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

использование остается прежним, и приведенный выше псевдокод дает учебное решение вашей проблемы. Реализация Java может выглядеть следующим образом:

// Construct set from first list:
Set<Integer> uniques = new HashSet<Integer>(list1);

// Iterate over second list, check each item’s existence in set.
for (int item : list2)
    if (! uniques.Contains(item))
        return item;

Обратите внимание, как это выглядит почти так же, как псевдокод. Решения на C #, C ++ или других языках не сильно отличаются.

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

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

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

Сделайте множества A, B из массивов a,b соответственно. A \ B дает дополнительное целое число в A. B \ A дает дополнительное целое число в B.

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