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

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

Вы можете сделать это с парой Hashsets, помогающих вам.

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

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

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

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

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

(хотя я не сортирую, этот алгоритм может быть очень легко модифицирован для создания алгоритма сортировки , которые сортируют в O (N + K) время и O (k ) пространство)

Если мы используем 32-битные беззнаковые C/C++ ints, то максимальное значение, которое может быть сохранено: 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-битных дюймов потребление памяти становится значительно больше, вместо массива в 16Кб нам нужен массив в 1Гб - возможно, менее практичный.

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

В псевдокоде :

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;

Если массив не отсортирован, вы не сможете выполнить 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

Где квадраты - это, скажем, HashSet.

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

Есть, по сути, два способа сделать это.

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

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

Из Java 5

Scanner sc = new Scanner();
sc.useDelimiter("\\D+"); // skip everything that is not a digit
List<Coord> result = new ArrayList<Coord>();
while (sc.hasNextInt()) {
    result.add(new Coord(sc.nextInt(), sc.nextInt()));
}
return result;

EDIT: Мы не знаем, сколько координат передано в строке coords .

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

def apply_permutation(lst, p):
    return [lst[x] for x in p]

arr=list("abcde")
new_order=[3,2,0,1,4]

print apply_permutation(arr,new_order)

Печать ['d', 'c', 'a', 'b', 'e'] .

Фактически создается новый список , но он может быть тривиально изменен для перестановки исходного «на месте».

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

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

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

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

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

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

2 * O ((n / 2) log (n / 2)) = O (nlog ( n / 2))

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

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

Алгоритмы сортировки по набору хешей и основанию системы счисления можно оптимизировать, учитывая три факта:

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

Если любое линейное сканирование обнаруживает совпадение, немедленно вернуть это совпадение.

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

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

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

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

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

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

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

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