Поиск двух массивов для совпадений, без дополнительной памяти

Ответ 1

Не существует O (1) пространственного метода для нахождения пересечения двух несортированных множеств в O (n) времени.

Для типа данных с неограниченным диапазоном минимальная цена сортировки равна O (n ln n).

Для типа данных с ограниченным диапазоном сортировка по радиусу обеспечивает возможность выполнять сортировку по месту в месте в O (n ln n 'n ") времени, где n - размер данных, n' - это число значений, которые могут быть представлены, а n" связано со стоимостью проверки того, находятся ли два значения в одной группе счисления. N "временная цена может быть сброшена в обмен на стоимость O (ln n).

В специальном случае из 32-битных целых чисел n 'равно 2 ^ 32, а n "равно 1, поэтому это сработает до O (n) и обеспечит выигрышное решение для многомиллиардных наборов записей.

Для целых чисел неограниченного размера n 'и n "исключают решение времени O (n) через radix.

Ответ 2

Ключ должен сортировать два массива на месте. Я выполнил поиск "сортировки по месту на месте" и нашел In-Place Radix Sort. Я считаю, что проблема разрешима, по крайней мере, для Java int [], применяя эти идеи для сортировки каждого массива по частям, а затем делая очевидное сканирование.

Кстати, я думаю, что правильный результат для проблемы в вопросительном коде - 1, 2, 3.

Вот моя реализация, основанная на ответах на упомянутый вопрос:

    public class ArrayMatch {
      public static void main(String[] args) {
        int[] a = { 4, 1, 2, 3, 4 };
        int[] b = { 2, 5, 6, 7, 3, 2, 2, 2, 2, 1, 2, 2, 2, 2 };
        System.out.print("Original problem");
        printMatches(a, b);
        System.out.println();

        int[] a1 = { 4, 1, -1234, 2, 3, 4, Integer.MIN_VALUE };
        int[] b1 = { -1234, 2, 5, 6, 7, 3, 2, 2, 2, 2, 1, 2, 2, 2, 2 , Integer.MIN_VALUE, Integer.MAX_VALUE};
        System.out.print("With negatives");
        printMatches(a1, b1);
        System.out.println();

      }

      // Print all matching elements between the two arrays.
      private static void printMatches(int[] a, int[] b) {
        if (a.length == 0 || b.length == 0) {
          return;
        }

        sort(a);
        sort(b);

        int i = 0;
        int j = 0;
        while (true) {
          while (a[i] < b[j]) {
            i++;
            if (i == a.length) {
              return;
            }
          }
          while (a[i] > b[j]) {
            j++;
            if (j == b.length) {
              return;
            }
          }

          if (a[i] == b[j]) {
            System.out.print(" " + a[i]);

            do {
              i++;
            } while (i < a.length && a[i - 1] == a[i]);

            do {
              j++;
            } while (j < b.length && b[j - 1] == b[j]);
          }

          if (i == a.length || j == b.length) {
            return;
          }
        }
      }

      // In place radix sort.
      private static void sort(int[] in) {
        // Flip the sign bit to regularize the sort order
        flipBit(in, 31);
        sort(in, 0, in.length, 31);
        // Flip back the sign bit back to restore 2 complement
        flipBit(in, 31);
      }

      /**
       * Sort a subarray, elements start through end-1 of in, according to the
       * values in firstBit through 0.
       * 
       * @param in
       * @param start
       * @param end
       * @param firstBit
       */
      private static void sort(int[] in, int start, int end, int firstBit) {
        if (start == end) {
          return;
        }
        int mask = 1 << firstBit;
        int zeroCount = 0;
        for (int i = start; i < end; i++) {
          if ((in[i] & mask) == 0) {
            zeroCount++;
          }
        }

        int elements = end - start;
        int nextZeroIndex = start;
        int nextOneIndex = start + zeroCount;

        int split = nextOneIndex;

        if (zeroCount > 0 && zeroCount < elements) {
          while (nextZeroIndex < split) {
            if ((in[nextZeroIndex] & mask) != 0) {
              // Found a one bit in the zero area, look for its partner in the one
              // area
              while ((in[nextOneIndex] & mask) != 0) {
                nextOneIndex++;
              }
              int temp = in[nextZeroIndex];
              in[nextZeroIndex] = in[nextOneIndex];
              in[nextOneIndex] = temp;
              nextOneIndex++;
            }
            nextZeroIndex++;
          }

        }

        if (firstBit > 0) {
          sort(in, start, split, firstBit - 1);
          sort(in, split, end, firstBit - 1);
        }

      }

      private static void flipBit(int[] in, int bitNo) {
        int mask = 1 << bitNo;
        for (int i = 0; i < in.length; i++) {
          in[i] ^= mask;
        }
      }
    }

Ответ 3

Один из возможных ответов аналогичен решению HashMap... IF, вы знаете, что целые числа находятся в очень маленьком окне. Это было бы похоже на следующее: http://en.wikipedia.org/wiki/Bucket_sort

В принципе, если целые числа гарантированно находятся в определенном окне с постоянным размером (т.е. все они равны 1-1000), вы можете сделать это в постоянном пространстве, увеличивая каждую ячейку индекса = независимо от вашего номера. Это точно так же, как решение HashMap, за исключением того, что вам не нужно учитывать все возможные целые числа, такие как HashMap can, что позволяет сэкономить место. Если это неясно, дайте мне знать в комментариях, и я объясню далее.

Ответ 4

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

Основная идея - сделать хэширование на месте. Хеширование на месте может быть реализовано путем разбиения массива вокруг подходящего процентиля, например, на 90-е, используя алгоритм выбора O(n) медианы медианов. Это делит массив на небольшую часть (около 10%) и большую часть (около 90%), элементы которой отличаются друг от друга (меньше, чем элемент раздела или нет). Вы можете затем хэш из 10% -ной части в 90% -ую часть путем замены. Это хеширование может использоваться для обнаружения дубликатов. Это O(n) для каждой обработки 10% массива, поэтому сделано 10 раз все еще O(n). Я описал это гораздо более подробно, хотя с некоторым размахиванием руками я хотел бы исправить один день, в этот связанный вопрос..

Для этой конкретной проблемы вам нужно сделать 3-х разное на месте. Сначала на каждом отдельном массиве удалять дубликаты. Затем на обертке, представляющей объединенные массивы (если индекс меньше длины массива 1, индекс в массив 1, иначе индексируйте в массив 2), чтобы сообщать о дубликатах.