【c++leetcode】69. Sqrt(x)

本文主要是介绍【c++leetcode】69. Sqrt(x)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

问题入口

二分搜索

最困难的是能否意识到用二分搜索法解题。

算术平方根的区间在[1, x] 。代码如下：

class Solution {
public:int mySqrt(int x) {if (x == 1 || x == 0){return x;}int64_t start = 1;int64_t end = x;while (start <= x){int64_t mid = start + (end - start) / 2;if (mid * mid  < x){if ((mid + 1) * (mid + 1) > x)return mid;start = mid + 1;}else if(mid * mid  > x){if ((mid - 1) * (mid - 1) < x)return mid - 1;end = mid - 1;}elsereturn mid;}return 0;}
};

关于时间复杂度

以中间的元素为界，如果大于中间元素，范围限定在右半边，如果小于中间元素，范围限定在左半边。假设数组元素数为n，范围依次是。假设通过k次找到指定元素， 。时间复杂度为O(logn)

溢出

题目要求

#include <cstdint>
#include <iostream>int main() {int8_t a = INT8_MAX;int16_t b = INT16_MAX;int32_t c = INT32_MAX;int64_t d = INT64_MAX;std::cout << "Maximum value of int8_t: " << +a << std::endl;std::cout << "Maximum value of int16_t: " << b << std::endl;std::cout << "Maximum value of int32_t: " << c << std::endl;std::cout << "Maximum value of int64_t: " << d << std::endl;return 0;
}

假设 mid * mid(中间元素*中间元素) > 214783647，就会引发整数溢出。

所以 这里设置的数据类型是int64_t

这篇关于【c++leetcode】69. Sqrt(x)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---