(3)剑指Offer之数值的整数次方和调整数组元素顺序

一 数值的整数次方

题目描述:

给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。

问题解析:

这道题算是比较麻烦和难一点的一个了。我这里采用的是二分幂思想,当然也可以采用快速幂
更具剑指offer书中细节,该题的解题思路如下:
1.当底数为0且指数<0时,会出现对0求倒数的情况,需进行错误处理,设置一个全局变量;
2.判断底数是否等于0,由于base为double型,所以不能直接用==判断
3.优化求幂函数(二分幂)。
当n为偶数,a^n =(a^n/2)*(a^n/2);
当n为奇数,a^n = a^[(n-1)/2] a^[(n-1)/2] a。时间复杂度O(logn)

时间复杂度:O(logn)

示例代码:

public class Solution { 
      boolean invalidInput=false;    
      public double Power(double base, int exponent) {
          //如果底数等于0并且指数小于0
          //由于base为double型,不能直接用==判断
        if(equal(base,0.0)&&exponent<0){
            invalidInput=true;
            return 0.0;
        }
        int absexponent=exponent;
         //如果指数小于0,将指数转正
        if(exponent<0)
            absexponent=-exponent;
         //getPower方法求出base的exponent次方。
        double res=getPower(base,absexponent);
         //如果指数小于0,所得结果为上面求的结果的倒数
        if(exponent<0)
            res=1.0/res;
        return res;
  }
    //比较两个double型变量是否相等的方法
    boolean equal(double num1,double num2){
        if(num1-num2>-0.000001&&num1-num2<0.000001)
            return true;
        else
            return false;
    }
    //求出b的e次方的方法
    double getPower(double b,int e){
        //如果指数为0,返回1
        if(e==0)
            return 1.0;
        //如果指数为1,返回b
        if(e==1)
            return b;
        //e>>1相等于e/2,这里就是求a^n =(a^n/2)*(a^n/2)
        double result=getPower(b,e>>1);
        result*=result;
        //如果指数n为奇数,则要再乘一次底数base
        if((e&1)==1)
            result*=b;
        return result;
    }
}

当然这一题也可以采用笨方法:累乘。不过这种方法的时间复杂度为O(n),这样没有前一种方法效率高。

    // 使用累乘
    public double powerAnother(double base, int exponent) {
        double result = 1.0;
        for (int i = 0; i < Math.abs(exponent); i++) {
            result *= base;
        }
        if (exponent >= 0)
            return result;
        else
            return 1 / result;
    }

二 调整数组顺序使奇数位于偶数前面

题目描述:

输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有的奇数位于数组的前半部分,所有的偶数位于位于数组的后半部分,并保证奇数和奇数,偶数和偶数之间的相对位置不变。

问题解析:

这道题有挺多种解法的,给大家介绍一种我觉得挺好理解的方法:
我们首先统计奇数的个数假设为n,然后新建一个等长数组,然后通过循环判断原数组中的元素为偶数还是奇数。如果是则从数组下标0的元素开始,把该奇数添加到新数组;如果是偶数则从数组下标为n的元素开始把该偶数添加到新数组中。

示例代码:

时间复杂度为O(n),空间复杂度为O(n)的算法

public class Solution {
    public void reOrderArray(int [] array) {
        //如果数组长度等于0或者等于1,什么都不做直接返回
        if(array.length==0||array.length==1) 
            return;
        //oddCount:保存奇数个数
        //oddBegin:奇数从数组头部开始添加
        int oddCount=0,oddBegin=0;
        //新建一个数组
        int[] newArray=new int[array.length];
        //计算出(数组中的奇数个数)开始添加元素
        for(int i=0;i<array.length;i++){
            if((array[i]&1)==1) oddCount++;
        }
        for(int i=0;i<array.length;i++){
            //如果数为基数新数组从头开始添加元素
            //如果为偶数就从oddCount(数组中的奇数个数)开始添加元素
            if((array[i]&1)==1) 
                newArray[oddBegin++]=array[i];
            else newArray[oddCount++]=array[i];
        }
        for(int i=0;i<array.length;i++){
            array[i]=newArray[i];
        }
    }
}

欢迎关注我的微信公众号(分享各种Java学习资源,面试题,以及企业级Java实战项目回复关键字免费领取):
(3)剑指Offer之数值的整数次方和调整数组元素顺序

上一篇:JS 日期格式化函数


下一篇:web.config connectionStrings 数据库连接字符串的解释