剑指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
推荐阅读
-
剑指offer:调整数组顺序使奇数位于偶数前面
-
剑指offer_数组_调整数组顺序使奇数位于偶数前面
-
剑指offer 12、13:数值的整数次方、调整数组顺序使奇数位于偶数前面
-
剑指Offer_编程题_调整数组顺序使奇数位于偶数前面
-
剑指offer - 12.调整数组顺序使奇数位于偶数前面
-
剑指offer 12 --调整数组顺序,使奇数位于偶数前面
-
调整数组顺序使奇数位于偶数前面 - 牛客剑指offer 12
-
JavaScript版《剑指offer》刷题(12)调整数组顺序使奇数位于偶数前面
-
剑指offer 面试题12 调整数组顺序使奇数位于偶数前面
-
剑指offer_12调整数组使奇数位于偶数的前面(Java版)