Различные подходы к решению проблемы
Подход 1.Использование встроенных методов
Подход 2.Используйте все натуральные числа от 1.
- Если число равно 0 или 1, то вернуть число
- Создайте две переменные, одна будет счетчиком, а другая будет хранить квадраты счетчика.
- Цикл до квадрата счетчика меньше или равен заданному числу
- Увеличьте переменную счетчика на единицу и обновите значение другой переменной.
- Вернуть счетчик
Временная сложность:O(√n)
Пространственная сложность:O(1)
Подход 3.Двоичный поиск
- Эта функция примет число (x) в качестве аргумента
- Создайте две переменные, low и high, и инициализируйте их значениями 0 и x.
- Создайте цикл с условием
low < high - Найдите среднее значение
floor((low + high) / 2) - Если квадрат mid-value равен x, возвратить mid
- Если больше x,
high = mid - 1 - В противном случае
low = mid + 1 - Если
x < high * highвернутьhigh - 1 - В противном случае вернуть
high
Примечание. Мы берем высокое значение floor(high/2), поскольку нижний предел квадратного корня из x не может быть больше x/2, когда x > 1.
Временная сложность:O(log n)
Пространственная сложность:O(1)
Также читайте,
