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

Question

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

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

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

Answer 1

Если я правильно понимаю проблему, вы должны проверить, есть ли указанное число в массиве.И не найти все числа в массиве, которые имеют свои квадраты в массиве тоже.Просто сохраните два логических значения (одно для проверки, найдено ли число, другое для квадрата), итерируйте по элементам в массиве и протестируйте каждый элемент.Возвращает 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;

Answer 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), а затем использовать этот метод для проверки квадратов, которые все равно будут быстрее, чем простое решение для достаточно большого набора данных.