題目描述

實現(xiàn)函數(shù)double Power(double base, int exponent)，求base的exponent次方。不得使用庫函數(shù)，同時不需要考慮大數(shù)問題。

示例 1:

輸入: 2.00000, 10
輸出: 1024.00000
示例 2:

輸入: 2.10000, 3
輸出: 9.26100
示例 3:

輸入: 2.00000, -2
輸出: 0.25000
解釋: 2-2 = 1/22 = 1/4 = 0.25

說明:

-100.0 < x < 100.0
n 是 32 位有符號整數(shù)，其數(shù)值范圍是 [?231, 231 ? 1] 。

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/shu-zhi-de-zheng-shu-ci-fang-lcof

解題思路

本題采用快速冪法，將x^n分n為奇數(shù)和偶數(shù)進行不同計算，可實現(xiàn)時間復雜度O(logn)的解法，同時由于在C語言將負整數(shù)轉(zhuǎn)換為正整數(shù)時，可能會有溢出情況，通過unsigned int m = (unsigned int)n轉(zhuǎn)換排除溢出問題。

代碼

double myPow(double x, int n){
    double res;

    if(x == 0)
        return 0;

    unsigned int m = (unsigned int)n;
    if(n < 0)
    {
        m = -m;
        x = 1 / x;
    }

    res = 1;
    while(m)
    {
        if(m & 1)
            res *= x;
        x *= x;
        m >>= 1;
    }

    return res;
}

測試代碼及結果

#include<stdio.h>
double myPow(double x, int n);

int main(void)
{
    printf("x = 2.1, n = 0, res = %lf\n", myPow(2.1, 0));
    printf("x = 2.1, n = 3, res = %lf\n", myPow(2.1, 3));
    printf("x = 2.1, n = -3, res = %lf\n", myPow(2.1, -3));
    printf("x = -2.1, n = 3, res = %lf\n", myPow(-2.1, 3));
    printf("x = -2.1, n = -3, res = %lf\n", myPow(-2.1, -3));
    printf("x = -2.1, n = 0, res = %lf\n", myPow(-2.1, 0));
    printf("x = 0.0, n = 3, res = %lf\n", myPow(0.0, 3));
    printf("x = 0.0, n = -3, res = %lf\n", myPow(0.0, - 3));
    printf("x = 0.0, n = 0, res = %lf\n", myPow(0.0, 0));

    return 0;
}

執(zhí)行結果

時間復雜度：O(logn)，空間復雜度：O(1)。