Алгоритм нахождения числа и его квадрата в массиве

Question

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

Я пытался сделать это сам, но мне удалось найти решение только в O (n ² ).

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

Answer 1

создать новый массив в два раза длиннее входного массива. O (2N)
скопировать все числа в O (N)
скопировать квадраты чисел в O (N)
радикальная сортировка (мы можем, так как они все целые) O (N)
повторить один раз, чтобы увидеть, есть ли два числа одно и то же после другого O (N)
прибыль! O (1)

Answer 2

Есть два основных способа сделать это.

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

2. Вставить все элементы массива в хеш-таблицу (или любую быструю set структуру данных). Затем снова выполните итерации по элементам массива, проверяя, существует ли его квадрат в хеш-таблице. Использование хеш-таблицы дает общую сложность O (n), но вам потребуется O (n) дополнительного пространства. Вы также можете использовать древовидный set (например, std::set в C ++ или TreeSet в Java), что даст вам сложность O (nlogn).

Answer 3

Если мы допустим, что входные данные могут быть отсортированы по O (N) по радикальной сортировке, я бы немного улучшил решение Криса:

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

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

В ответ на комментарий спрашивающего о другом ответе: если целые числа на входе не ограничены, то я не думаю, что это можно сделать. Простое вычисление квадрата целого числа требует большего, чем линейное время (по крайней мере: линейный алгоритм умножения не известен), поэтому рассмотрим ввод размером n битов, состоящий из двух целых чисел размером n / 3 бит и 2 * n / 3 бит. Проверка, является ли один квадратом другого, не может быть выполнена в O (n). Я думаю. Я могу ошибаться.

Answer 4

Примечания по оптимизации

Оба алгоритма сортировки по хэш-сетам и основам сортировки можно оптимизировать, отметив три факта:

1. Нечетные и четные значения могут обрабатываться отдельно
2. Вычисление целочисленного квадратного корня - очень быстрая операция (обычно состоит из 3-5 делений и нескольких сложений)
3. Локальность кэша важна для обоих этих алгоритмов

Приведенные ниже оптимизированные алгоритмы обычно работают в 5 раз быстрее и используют менее половины ОЗУ в неоптимизированном случае. В некоторых случаях, когда размер данных подобен размеру кэша L2 / L3, они могут работать в 100 раз быстрее или более.

Оптимизированный алгоритм на основе радикальной сортировки

Структура данных состоит из пяти списков целых чисел: IN, Aodd, Bodd, Aeven, Beven Списки A и B используют половину целочисленного размера IN. (например, если IN = 64 бита, A & B = 32 бита)

1. Сканирование списка IN, чтобы найти самые большие нечетные и четные числа MAXodd и MAXeven
2. Пусть LIMITodd = этаж (sqrt (MAXodd))
3. Let LIMITeven = floor (sqrt (MAXeven))
4. Для каждого номера в списке IN: a. Вычислить квадратный корень, если положительный. Если точно, добавьте квадратный корень в список Aodd / Aeven. б. Если число> = 0 и <= LIMITodd / LIMITeven, добавьте его в список Bodd / Beven </li>
5. Список сортировки по радиксу Aodd и Bodd с использованием всего лишь log2 (LIMITodd) битов
6. Линейное сканирование Аодда и Бодда на совпадение
7. Список сортировки Radix Aeven и Beven, использующий только log2 (LIMITeven) биты
8. Линейное сканирование Эйвена и Бевена на совпадение

Если при линейном сканировании совпадение найдено, немедленно верните это совпадение.

Причина, по которой это намного быстрее, чем простой алгоритм сортировки по основанию, заключается в том, что:

• Как правило, сортируемые массивы имеют менее 1/4 числа значений и требуют только половину числа бит на целое число, так что в общей сложности менее 1/8 ОЗУ используется в данном виде, что хорошо для кеш.
• Радикальная сортировка выполняется на гораздо меньшем количестве битов, что приводит к меньшему количеству проходов, поэтому, даже если она превышает ваш кэш L1 или L2, вы читаете ОЗУ меньше и вы читаете гораздо меньше ОЗУ
• Линейное сканирование обычно выполняется намного быстрее, поскольку список A содержит только точные квадратные корни, а список B содержит только небольшие значения

Оптимизированный алгоритм на основе хэширования

Структура данных - это список целых чисел IN, плюс два хэш-набора A и B Наборы A и B используют половину целочисленного размера IN

1. Сканирование списка IN, чтобы найти самые большие нечетные и четные числа MAXodd и MAXeven
2. Пусть LIMITodd = floor (sqrt (MAXodd))
3. Let LIMITeven = floor (sqrt (MAXeven))
4. Для каждого нечетного числа в списке IN: a. Вычислить квадратный корень, если положительный. Если точно, проверьте, существует ли квадратный корень в B, и верните, если true, в противном случае добавьте его в A. b. Если число> = 0 и <= LIMITodd / LIMITeven, проверьте, существует ли оно в A, и верните, если true, в противном случае добавьте его в B. </li>
5. Очистите A и B и повторите шаг 4 для четных чисел

Причина, по которой это быстрее, чем простой алгоритм хэширования, заключается в том, что:

• Хэш-набор обычно составляет 1/8 объема ОЗУ, что приводит к гораздо лучшей производительности кеша
• Только точные квадраты и маленькие числа имеют записи хэш-набора, поэтому гораздо меньше времени тратится на хэширование и добавление / удаление значений

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

Answer 5

Без сортировки, работает с дубликатами:

Итерируйте массив, чтобы найти самые маленькие и самые большие целые числа. О (п)
Создайте массив битов размером с разницу. O (1) время, O (k) пробел
(Теперь каждое возможное целое число между наименьшим и наибольшим значениями имеет соответствующий бит в массиве)
Повторяйте старый массив, устанавливая бит, соответствующий каждому найденному целому числу, равному 1. O (n)
Повторите итерацию старого массива снова, проверяя, установлен ли для целочисленного квадрата соответствующий бит. О (п)

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

Answer 6

Если мы используем C / C ++ 32-битные беззнаковые целые, максимальное значение, которое можно сохранить: 4294967295 = (2 << 32) -1.Наибольшее число, квадрат которого мы можем сохранить, равно (1 << 16) -1 = 65535.Теперь, если создать массив битов и сохранить в массиве, видели ли мы число и / или его квадрат (2 бита на «слот»), мы можем уменьшить общее хранилище до 65535/4 = 16384 байта. </p>

IMO Это не чрезмерное потребление памяти, поэтому мы должны быть в состоянии сделать это без радикальной сортировки.Алгоритм O (N) может выглядеть следующим образом:

uint32_t index(uint32_t i ) { return i/4; }
unsigned char bit1( uint32_t i ) { return 1<<( (i%4)*2 ); }
unsigned char bit2( uint32_t i ) { return 1<<( (i%4)*2 +1 ); }


bool hasValueAndSquare( std::vector<uint32_t> & v )
{
   const uint32_t max_square=65535;

   unsigned char found[(max_square+1)/4]={0};
   for(unsigned int i=0; i<v.size(); ++i)
   {
      if (v[i]<=max_square)
      {
          found[ index(v[i]) ] |= bit1(v[i]);
          if ((found[ index(v[i])] & bit2(v[i])) == bit2(v[i])) return true;
      }
      uint32_t w = (uint32_t)round(sqrt(v[i]));
      if( w*w == v[i] )
      {
          found[ index(w) ] |= bit2(w);
          if ((found[index(w)] & bit1(w)) == bit1(w)) return true;
      }
    }
    return false;
 }

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

Обратите внимание, что если мы используем 64-битные целые числа, потребление памяти становится намного больше, вместо массива 16 КБ нам нужен массив 1 ГБ - возможно, менее практичный.

Answer 7

Лично я думаю, что ответ Анона (маленький алгоритм с «квадратами») более полезен, чем кажется: уберите из него строку «убрать все меньше, чем е из квадратов», и алгоритм может обработать несортированный ввод массив.

Если мы предположим, что типичная машина домашней работы с достаточным пространством, структура данных 'квадратов' может быть смоделирована как массив логических флагов, что дает истинное O (1) время поиска.

Answer 8

Вы можете сделать это с помощью нескольких хэш-наборов, которые вам помогут.

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

Answer 9

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

Answer 10

1) С хэш-картой вы получите O (n).

2) Если вы используете std :: set для 2 сетов: четных и шансов, вы можете получить

2 * O ((N / 2) журнал (п / 2)) = O (Nlog (п / 2))

если предположить, что число шансов примерно равно числу