У меня есть массив целых чисел, и мне нужен алгоритм O (n), чтобы найти, содержит ли массив число и его квадрат; достаточно одной пары.
Я попытался сделать это сам, но мне удалось найти решение в O (n 2).
Я думал об использовании сортировки, но использование памяти слишком велико.
создать новый массив в два раза больше длины входного массива. O (2N)
скопируйте все числа в O (N)
скопируйте квадраты чисел в O (N)
radix sort (мы можем, так как они все ints) O (N)
повторяйте один раз, чтобы увидеть, есть ли два числа один и тот же один после другого O (N)
прибыль! O (1)
В основном есть два способа сделать это.
Сортируйте массив и затем выполните двоичный поиск квадрата каждого числа. Общая сложность была бы O (nlogn), но для этого потребовалась бы сортировка, которая бы уничтожила первоначальный порядок (что может быть важно для вашего случая).
Вставьте все элементы массива в хэш-таблицу (или любую быструю структуру данных set). Затем снова перебираем элементы массива, проверяя, существует ли его квадрат в хэш-таблице. Использование хэш-таблицы дает общую сложность O (n), но вам понадобится дополнительное пространство O (n). Вы также можете использовать древовидный set (например, std::set в С++ или TreeSet в Java), что даст вам сложность O (nlogn).
Если нам разрешено считать, что вход может быть отсортирован в O (N) по методу radix, я бы немного улучшил решение Chris:
Каждый из двух "указателей" движется строго вперед, поэтому общая сложность - это O (N), предполагая, что радиальная сортировка - это O (N), а квадратура и сравнение - O (1). Предположительно, тот, кто задал вопрос, предполагал, что эти предположения будут сделаны.
В ответ на комментарий эксперта по другому ответу: если целые числа на входе не ограничены, то я не думаю, что это можно сделать. Простое вычисление квадрата целого требует больше, чем линейного времени (по крайней мере: нет линейного алгоритма для умножения), поэтому рассмотрим входные биты размера n, состоящие из двух целых чисел размером n / 3 bits и 2 * n / 3 бит. Проверка того, является ли один квадрат другого, не может быть выполнена в O (n). Я думаю. Я мог ошибаться.
Пока я не могу добавить к приведенным выше предложениям, вы можете уменьшить среднее время выполнения, сначала найдя минимальные и максимальные значения в своем наборе данных (как O (n)), так и ограничив свой поиск в этом диапазоне. Например, если максимальное значение равно 620, я знаю, что целое число 25 или более не имеет квадрата в списке.
Вы можете сделать это с помощью нескольких хешсет, которые помогут вам.
Во время итерации, Если значение находится в квадрате hashset, у вас есть пара (значение представляет собой квадрат ранее найденного значения) Если квадрат находится в значениях hashset, у вас есть пара (квадрат этого значения уже был пройден) иначе сохраните значение в одном и в квадрате в другом.
Лично я думаю, что ответ Анона (маленький алгоритм с "квадратами" ) более полезен, чем кажется: удалите из него строку "удалить все меньше, чем е из квадратов", и алгоритм может обрабатывать несортированный вход массив.
Если мы предположим, что типичная машина Homework с достаточным пространством, структура данных квадратов может быть смоделирована как массив булевых флагов, что дает истинное время поиска O (1).
Если мы используем 32-битные unsigned ints C/С++, максимальное значение, которое может быть сохранено: 4294967295 = (2 < 32) -1. Наибольшее число, квадрат которого мы можем сохранить, равен (1 < 16) -1 = 65535. Теперь, если создать массив бит и сохранить в массиве, видели ли мы число и/или его квадрат (2 бит на "слот" ), мы можем получить общее хранилище до 65535/4 = 16384 байт.
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-битные ints, потребление памяти становится намного больше, вместо массива 16Kb нам нужен массив 1Gb - возможно менее практичный.
Без сортировки работает с дубликатами:
Итерируйте массив, чтобы найти наименьшие и наибольшие целые числа. О (п)
Создайте массив бит, размер разницы. O (1) время, O (k) пространство
(Теперь каждое возможное целое число между наименьшим и самым большим значением имеет соответствующий бит в массиве)
Итерируйте старый массив, установив бит, соответствующий каждому целому числу, найденному в 1. O (n)
Итерируйте старый массив снова, проверяя, имеет ли целочисленный квадрат соответствующий бит. О (п)
(Хотя я не сортировал, этот алгоритм может быть очень легко модифицирован, чтобы создать алгоритм сортировки, который сортирует в O (n + k) время и O (k) пробел)
Примечания по оптимизации
Оба алгоритма сортировки hashset и radix можно оптимизировать, отметив три факта:
Оптимизированные алгоритмы ниже обычно выполняются в 5 раз быстрее и используют менее половины ОЗУ неоптимизированного случая. В некоторых случаях, когда размер данных аналогичен размеру кеша L2/L3, он может выполнять 100 раз быстрее или более.
Оптимизированный алгоритм, основанный на сортировке счисления
Структура данных - это пять списков целых чисел: IN, Aodd, Bodd, Aeven, Beven В списках A и B используется половина целочисленного размера IN. (например, если IN = 64 бит, A и B = 32 бит)
Если любое линейное сканирование находит совпадение, немедленно возвращайте его.
Причина, по которой это происходит намного быстрее, чем простой алгоритм сортировки оснований, заключается в следующем:
Оптимизированный алгоритм на основе hashset
Структура данных - это список целых чисел IN, плюс два хэш-набора A и B Множества A и B используют половину целочисленного размера IN
Причина, по которой это быстрее, чем простой алгоритм хэширования, заключается в следующем:
Существует небольшая небольшая оптимизация, доступная здесь: A и B могут быть одним хэш-множеством, который хранит бит-флаг с каждой записью, чтобы сказать, является ли целое число в или B (оно не может быть в обоих, потому что тогда алгоритм было бы прекращено).
Если я правильно понимаю проблему, вам нужно проверить, указано ли указанное число в массиве. И не найти все числа в массиве, которые также имеют свой квадрат в массиве. Просто поддерживайте два логических значения (один, чтобы проверить, было ли найдено число, другое для квадрата), итерации по элементам в массиве и проверка каждого элемента. Верните AND из двух булевых.
В псевдокоде:
bool ArrayContainsNumberAndSquare(int number, int[] array):
boolean numberFound, squareFound;
int square = number * number;
foreach int i in array
(
numberFound = numberFound || i == number;
squareFound = squareFound || i == square;
)
return numberFound && squareFound;
1) С помощью hashmap вы получаете O (n).
2) Если вы используете std:: set на 2 наборах: evens и коэффициенты, вы можете получить
2 * О ((N/2) журнал (п/2)) = O (Nlog (п/2))
предполагая, что существует примерно столько же, сколько коэффициентов
Если массив не отсортирован, вы не сможете выполнить O (n).
Если он отсортирован, вы можете использовать это свойство, чтобы сделать это за один проход, например:
foreach e in array
if squares contains e
return true
remove all less than e from squares
add e * e to squares
return false
Где squares есть, скажем, HashSet.
Если он не отсортирован, вы можете отсортировать его в O (n log n), а затем использовать этот метод для проверки квадратов, которые будут по-прежнему быстрее, чем наивное решение на достаточно большом наборе данных.