Очень сложная задача алгоритма сортировки - время O (n) - сложность времени

Question

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

Представьте, что у нас есть 2 несортированных целочисленных массива.Длина обоих массивов равна n, и они содержат целые числа в диапазоне от 0 до n 765 (максимум n 765).

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

дубликаты в одном массиве невозможны

Любая помощь и идея приветствуются.

Answer 1

То, что вы хотите, невозможно. Каждый элемент будет сохранен в количестве до log (n ^ 765) битов, что равно O (log n). Поэтому простое чтение содержимого обоих массивов займет O (n * logn).

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

Редактировать

Решение, которое вы можете найти, заключается в использовании radix sort для сортировки ваших данных, после чего вы можете легко проверить наличие дублирующих элементов. Вы бы посмотрели на свои числа в базе n, и сделаете 765 проходов над вашими данными. Каждый проход будет использовать сортировку ведра или сортировку по счету для сортировки по одной цифре (в базе n). Этот процесс будет занимать O (n) время в худшем случае (при условии постоянной верхней границы на размер элемента). Обратите внимание, что я сомневаюсь, что кто-нибудь когда-нибудь выберет это вместо хеш-таблицы.

Answer 2

Предполагая, что умножение и деление равно O (1):

Думая о числах, вы можете записать их как:

Число (i) = A0 * n ^ 765 +A1 * n ^ 764 + .... + A764 * n + A765.

для кодирования числа в этот формат, вы должны просто сделать Number / n ^ i, Number% n ^ i, еслиВы предварительно вычислите, n ^ 1, n ^ 2, n ^ 3, ... это можно сделать в O (n * 765) => O (n) для всех чисел.предварительное вычисление n ^ i, может быть выполнено в O (i), поскольку i не более 765, это O (1) для всех элементов.

Теперь вы можете записать Numbers (i) в виде массива: Nembers (i) = (A0, A1, ..., A765) и знать, что вы можете изменить элементы сортировки:

сначала сравните всеA765, затем ...., Все значения Ai находятся в диапазоне 0..n, поэтому для сравнения значений Ai можно использовать Отсчет для сортировки (Отсчет для подсчета равен O (n)), поэтому сортировка по основанию равна O(n * 765), то есть O (n).

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

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

Редактировать: для уточнения того, как вы можете найти похожие элементы в 2-отсортированных списках:

У вас есть 2 отсортированных списка, например, в сортировке слиянием, как вы можете объединить два отсортированных списка водин список?вы переместитесь из начала списка 1 и списка 2 и переместите указатель вашей головы в list1, в то время как head (list (1))> head (list (2)), и после этого сделайте это для list2 и ..., такесли есть подобный элемент, ваш алгоритм остановится (до достижения конца списков), или в конце двух списков ваш алгоритм остановится.

это так же просто, как показано ниже:

public int FindSimilarityInSortedLists(List<int> list1, List<int> list2)
{
   int i = 0;
   int j = 0;


   while (i < list1.Count && j < list2.Count)
   {
      if (list1[i] == list2[j])
         return list1[i];

      if (list1[i] < list2[j])
         i++;
      else
         j++;    
   }
   return -1; // not found
}

Answer 3

Если бы память была неограниченной, вы могли бы просто создать хеш-таблицу с целыми числами в качестве ключей и значениями, сколько раз они были найдены. Затем, чтобы выполнить «быстрый» поиск, вам нужно выполнить простой запрос на целое число, выяснить, содержится ли оно в хеш-таблице, и, если он найден, проверить, что значение равно 1 или 2. Это потребует O (n) для загрузки и O (1 ) к запросу.

Answer 4

Я не думаю, что вы можете сделать это O (n).Вы должны проверить n значений, находятся ли они в другом массиве.Это означает, что у вас есть n операций сравнения, по крайней мере, если в другом массиве всего 1 элемент.Но так как у вас есть n элементов в другом массиве, вы можете сделать это просто O (n * n)