算法-给整数数组重新排列的算法

小组事务管理 小组事务管理 主题:974 回复:1955

算法-给整数数组重新排列的算法

想挽留 发布于 2017-04-12 字数 156 浏览 1258 回复 6

给定一个存放整数的数组,重新排列数组使得数组左边为奇数,右边为偶数。
要求:空间复杂度O(1)

补充:这是面试题,理论上应该不能用语言自带函数

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

支持 Markdown 语法,需要帮助?

评论(6

甜柠檬 2017-10-25 6 楼

使用两个指针,一个指针p1指向数组中第一个元素,一个指针p2指向数组中第最后一个元素。当p1指向的是偶数时,就让p1++,直到指向奇数,当p2指向的是奇数时就让p1--,直到指向的是偶数,然后将换p1和p2的值,继续重复上述过程,直到p1与p2相遇就停止。

虐人心 2017-09-23 5 楼

经典算法,提供一个看起来比较简化的版本

 void partition(int a[], int n) {
int i = 0;
int j = n - 1;

while (i < j) {
while ((a[i]&1) == 1) ++i;
while ((a[j]&1) == 0) --j;
swap(a[i++], a[--j]);
}
}

void swap(int &a, int &b) {
int tmp = a;
a = b;
b = tmp;
}

虐人心 2017-09-19 4 楼

设F(n) = n % 2,然后看做是对整个数组做键值为F(n)的排序。特别之处在于只有0和1两种值,因此可以用快速排序的一次循环完成。
还有O(1)又不是不让你们用临时变量……

 int i = 0, j = N - 1;
while(i < j)
{
while((a[i]&1) && i < j) i++;
while(!(a[j]&1) && i < j) j--;
int temp = a[i];
a[i] = a[j];
a[j] = temp;
i++;j--; //要不要这行都行
}

清晨说ぺ晚安 2017-08-29 3 楼

a和b交换,不添加额外空间:
a = a ^ b;

b = a ^ b;

a = a ^ b;
当然 用加法减法也行。。
然后简单的冒泡即可....

夜无邪 2017-08-16 2 楼

代码如下

include <stdio.h>

include <stdlib.h>

// add by 白菜 2012-08-08 22:06:03
int main()
{
int arr[19]= {1,3,5,8,6,3,6,5,2,7,8,99,23,56,87,22,43,54,123};
int count=sizeof(arr)/sizeof(*arr);
int i=0,j=count-1;
while(i<j)
{
if(arr[i]%2==1 && i<j) i++;
if(arr[j]%2==0 && i<j) j--;
arr[i]=arr[i]^arr[j];
arr[j]=arr[i]^arr[j];
arr[i]=arr[i]^arr[j];

}
for(int k=0; k&lt;count; k++)
{
    printf("%d ",arr[k]);
}

}

甜柠檬 2017-05-08 1 楼

这样不知道否和要求不:

$arr = array(1,3,5,8,6,3,6,5,2,7,8,99,23,56,87,22,43,54,123);

for($i=0;$i&lt;count($arr);$i++) {
    if($arr[$i]%2 == 0) {
       array_push($arr,$arr[$i]);
       unset($arr[$i]);
    }
}

print_r($arr);

修改后:

$arr = array(1,3,5,8,6,3,6,5,2,7,8,99,23,56,87,22,43,54,123);

$len = count($arr);
$j = $len - 1;
for($i=0;$i&lt;$len &amp;&amp; $j&gt;$i;$i++) {

    if($arr[$i]%2 == 0) {
        $arr[$i] ^= $arr[$j];
        $arr[$j] ^= $arr[$i];
        $arr[$i] ^= $arr[$j];
        $j--;
        $i--;
    }
}

print_r($arr);