剑指offer 面试题14―调整数组顺序使奇数位于偶数前面
发布时间:2020-12-13 20:09:34 所属栏目:PHP教程 来源:网络整理
导读:题目: 输入1个整数数组,实现1个函数来调剂该数组中数组的顺序,使得所有奇数位于数组的前半部份,所有偶数位于数组的后半部份。 解法1:O(n^2) 从头扫描数组,每碰到1个偶数,拿出这个数字,并把位于这个数字后面的所有数字往前移动1位。挪完以后在数组的
题目: 输入1个整数数组,实现1个函数来调剂该数组中数组的顺序,使得所有奇数位于数组的前半部份,所有偶数位于数组的后半部份。
解法1:O(n^2) 从头扫描数组,每碰到1个偶数,拿出这个数字,并把位于这个数字后面的所有数字往前移动1位。挪完以后在数组的末尾有1个空位,这时候把该偶数放入这个空位中。 由于每碰到1个偶数就需要移动O(n)个数字,因此总的时间复杂度是O(n^2).
解法2:O(n) 类似快排,两个指针,1个指向数组头,只向后移动,1个指向数组尾,只向前移动。如果第1个指针指向的数字是偶数,并且第2个指针指向的数字是奇数,交换两数。
void foo(int a[],int left,int right)
{
if(left>right)
return;
int i,j;
i=left;
j=right;
while(i!=j)
{
while(a[j]%2==0&&i<j) j--;
while(a[i]%2!=0&&i<j) i++;
if(i<j)
swap(a[i],a[j]);//交换
}
} (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |