Open Cosen95 opened 4 years ago
这道题目最暴力的解法就是累乘,不过有点太粗糙了,略略略,,,
其实,采用分治
是比较合理的解决方案。
先分别判断n分别为负数、0、1的情况。
剩下的就是n为正数的情况了。但n可能为偶数和奇数,我们可以采用每次把n/2的方式去累乘,(奇数的最后需要再乘以本身)这样时间复杂度就大大降低了。
举个例子说明下。假设求解
Pow(2, 1024)
,如果用暴力求解,时间复杂度是1024,也就是O(n)
而用现在这种,时间复杂度对应是10,也就是O(logn)
/** * @param {number} x * @param {number} n * @return {number} */ var myPow = function(x, n) { // 小于0 if (n < 0) return 1 / myPow(x, -n) // 等于0 if (n === 0) return 1 // 等于1 if (n === 1) return x // 奇数 if (n%2 === 1) return myPow(x*x, Math.floor(n/2)) * x // 偶数 return myPow(x*x, Math.floor(n/2)) };
leetcode: https://leetcode-cn.com/problems/powx-n/