欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

剑指offer 12、13:数值的整数次方、调整数组顺序使奇数位于偶数前面

程序员文章站 2022-07-10 12:19:44
...

第十二题题目描述
给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。
思路:类似于第九题,快速幂运算。这一题要分析exponent为负数的情况,且base为0的情况。
复杂度:O(n)

class Solution {
public:
    double Power(double base, int exponent) {
        if(abs(base)<0.0000001 && exponent<=0)
            return 0;
        int expon=abs(exponent);
        double result=1;
        while(expon)//快速幂运算
        {
            if(expon&1)
                result*=base;
            base*=base;
            expon=expon>>1;
        }
        return exponent>0?result:1/result;
    }
};

# -*- coding:utf-8 -*-
class Solution:
    def Power(self, base, exponent):
        if exponent<=0 and (abs(base)<0.0000001) :
            return 0
        expon=abs(exponent)
        sum_all=1
        while expon:
            if expon & 1:
                sum_all*=base
            base*=base
            expon=expon>>1
        return sum_all if exponent>=0 else 1/sum_all

第十三题:
题目描述
输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有的奇数位于数组的前半部分,所有的偶数位于位于数组的后半部分,并保证奇数和奇数,偶数和偶数之间的相对位置不变。
思路:1.以空间换时间。把每个奇数依次存储在一个数组中,偶数存在另一个数组中,然后合并数组。
2.每次都把奇数放到第一个偶数之前,然后删除偶数后面的奇数。

复杂度O(n)
class Solution {
public:
    void reOrderArray(vector<int> &array) {
        if(array.empty())
            return;
        vector<int>even;
        int index=0;
        for(int i=0;i<array.size();++i)
        {
            if((array[i]&1)==1)
            {
                if(i!=index)
                    array[index]=array[i];
                ++index;
            }
            else
                even.push_back(array[i]);
        }
        for(int i=0;i<even.size();++i)
        {
            array[index+i]=even[i];
        }
    }
};
复杂度O(n^2)
插入排序
class Solution {
public:
    void reOrderArray(vector<int> &array) {
        if(array.empty())
            return;
        int len=array.size();
        for(int i=1;i<len;++i)
        {
            int temp=array[i];
            int j=i-1;
            for(;(j>=0) && (temp%2==1) && (array[j]%2==0);--j)
                array[j+1]=array[j];
            array[j+1]=temp;
        }
    }
};
python
# -*- coding:utf-8 -*-
class Solution:
    def reOrderArray(self, a):
        for i in range(1,len(a)):
            temp=a[i]
            j=i-1
            while j>=0 and a[j]%2==0 and temp%2==1:
                a[j+1]=a[j]
                j-=1
            a[j+1]=temp
        return a