Предложить эффективный алгоритм

Question

Имеется массив arr размером 100000, каждый элемент 0 <= arr[i] < 100. (не отсортировано, содержит дубликаты)

Узнайте, сколько триплетов (i,j,k) присутствует так, что arr[i] ^ arr[j] ^ arr[k] == 0 Примечание : ^ - оператор Xor. также 0 <= i <= j <= k <= 100000

У меня такое чувство, что мне нужно вычислить частоты и сделать некоторые вычисления, используя частоту, но я просто не могу начать.

Любой алгоритм лучше, чем очевидный O(n^3) приветствуется. :)

Это не домашняя работа. :)

Answer 1

Я думаю, что ключ в том, что вам не нужно определять i, j, k, просто посчитайте, сколько.

Инициализируйте размер массива 100

Цикл, хотя arr, подсчитывая, каксуществует множество значений: O (n)

Цикл по ненулевым элементам небольшого массива, определение того, какие тройки удовлетворяют условию - предположим, что счетчиками всех трех чисел являются A, B,C - количество комбинаций в исходном arr (A + B + C) /! A! B! C!- 100 ** 3 операции, но это все равно O (1) при условии, что 100 является фиксированным значением.

Итак, O (n).

Answer 2

Возможное решение O (100 * n) = O (n).это решает проблему I <= J <= K.Как вы знаете A ^ B = 0 <=> A = B, поэтому

long long calcTripletsCount( const vector<int>& sourceArray )
{
  long long res = 0;
  vector<int> count(128);
  vector<int> countPairs(128);
  for(int i = 0; i < sourceArray.size(); i++)
  {
    count[sourceArray[i]]++; // count[t] contain count of element t in (sourceArray[0]..sourceArray[i]) 
    for(int j = 0; j < count.size(); j++)
      countPairs[j ^ sourceArray[i]] += count[j]; // countPairs[t] contain count of pairs p1, p2 (p1 <= p2 for keeping order) where t = sourceArray[i] ^ sourceArray[j]
    res += countPairs[sourceArray[i]]; // a ^ b ^ c = 0 if a ^ b = c, we add count of pairs (p1, p2) where sourceArray[p1] ^ sourceArray[p2] = sourceArray[i]. it easy to see that we keep order(p1 <= p2 <= i)
  }  
  return res;
}

Извините за мой плохой английский ...

Answer 3

Возможное решение O (n ^ 2), если оно работает: Сохранить переменную count и два массива, single[100] и pair[100]. Итерируйте arr, и для каждого элемента значение n:

• обновление count: count += pair[n]
• update pair: итерация массива single и для каждого элемента индекса x и значения s != 0 do pair[s^n] += single[x]
• обновление single: single[n]++

В конце count содержит результат.

Answer 4

У меня есть (простое) O (n ^ 2 log n) решение, которое учитывает тот факт, что i, j и k относятся к индексам, а не к целым числам.

Простой первый проход позволяет нам построить массив A из 100 значений: значения -> список индексов, мы сохраняем список отсортированным для дальнейшего использования. O (n log n)

Для каждой пары i, j такой, что i <= j, мы вычисляем X = arr [i] ^ arr [j]. Затем мы выполняем бинарный поиск в A [X], чтобы определить количество индексов k, таких что k> = j. O (n ^ 2 log n)

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

Answer 5

Начните с подсчета частоты количества вхождений каждого числа от 1 до 100, как предлагает Павел.В результате получается массив freq [] длиной 100.

Далее, вместо зацикливания на тройках A, B, C из этого массива и проверки условия A ^ B ^ C = 0, зацикливание на парах A, Bс A Sum+=freq[A]*freq[B]*freq[C] Работа составляет O (n) для подсчета частоты, плюс около 5000 для цикла по A Так как каждая тройка из трех разные числа A, B, C должны встречаться в некотором порядке, каждая такая тройка находит ровно один раз.Далее вам нужно искать тройки, в которых два числа равны.Но если два числа равны, а xor трех из них равно 0, третье число должно быть нулем.Таким образом, это равносильно вторичному линейному поиску B по массиву подсчета частот, который подсчитывает количество случаев (A = 0, B = C <100).(Будьте очень осторожны с этим случаем, и особенно осторожно с делом B = 0. Счетчик не просто freq [B] ** 2 или freq [0] ** 3. Там есть небольшая проблема комбинаторики, скрывающаяся там.) </p> Надеюсь, это поможет!

Answer 6

Sort the array, keeping a map of new indices to originals. O(nlgn)
Loop over i,j:i<j. O(n^2)
  Calculate x = arr[i] ^ arr[j]
  Since x ^ arr[k] == 0, arr[k] = x, so binary search k>j for x. O(lgn)
  For all found k, print mapped i,j,k

O (n ^ 2 lgn)