首页 > 代码库 > 剑指OFFER之调整数组顺序使奇数位于偶数前面找(九度OJ1516)

剑指OFFER之调整数组顺序使奇数位于偶数前面找(九度OJ1516)

题目描述:

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

 

输入:

每个输入文件包含一组测试案例。
对于每个测试案例,第一行输入一个n,代表该数组中数字的个数。
接下来的一行输入n个整数。代表数组中的n个数。

 

输出:

对应每个测试案例,
输入一行n个数字,代表调整后的数组。注意,数字和数字之间用一个空格隔开,最后一个数字后面没有空格。

 

样例输入:
5
1 2 3 4 5
样例输出:
1 3 5 2 4

解题思路:

  首先,说一种时间复杂度为O(n),但是空间复杂度较高的。但是这种代码,肯定不会是面试官喜欢的
  我们申请另外两个数组,每次输入数据时,直接比对是奇数还是偶数,顺序存放在两个数组中,并记录下标的变化。最后两个数组顺序输出就行了,核心代码如下:
    for(i=0;i<n;i++){
            scanf("%d",&arr[i]);
            if(arr[i]%2 == 1){
                arr1[num_arr1++] = arr[i];
            }else{
                arr2[num_arr2++] = arr[i];
            }
        }
        for(i=0;i<num_arr1;i++){
            printf("%d ",arr1[i]);
        }
        for(i=0;i<num_arr2-1;i++){
            printf("%d ",arr2[i]);
        }

  代码:

#include <stdio.h>
#include <memory.h>
#define N 100000
int arr[N];
int arr1[N];
int arr2[N];
void diffoddandeven(int n);
int main(void){
    int n,i,num_arr1,num_arr2;
    while(scanf("%d",&n)!=EOF && n>0){
        num_arr1 = num_arr2 = 0;
        memset(&arr,0,sizeof(int)*N);
        memset(&arr1,0,sizeof(int)*N);
        memset(&arr2,0,sizeof(int)*N);
        for(i=0;i<n;i++){
            scanf("%d",&arr[i]);
            if(arr[i]%2 == 1){
                arr1[num_arr1++] = arr[i];
            }else{
                arr2[num_arr2++] = arr[i];
            }
        }
        for(i=0;i<num_arr1;i++){
            printf("%d ",arr1[i]);
        }
        for(i=0;i<num_arr2-1;i++){
            printf("%d ",arr2[i]);
        }
        printf("%d\n",arr2[num_arr2-1]);
    }
    return 0;
}
/**************************************************************
    Problem: 1516
    User: xhalo
    Language: C
    Result: Accepted
    Time:100 ms
    Memory:2084 kb
****************************************************************/

  第二种方法

  另一种思想,不开辟新的空间,直接在原始数组上,进行移动。但是考虑到前后的顺序不能变化,因此简单的哨兵替换思想就不可以了。这时候我们可以通过两个下标,进行数据元素的移动。

  首先,考虑到奇数排在前面,偶数在后面,因此我们遍历数组,找到第一个奇数,和第一个偶数。如果第一个奇数在偶数的后面,就替换他们的位置,及下标:

 while(arr[i]%2 == 0 && i<n){
        i++;
        flag = 1;
    }
    int j=0;
    while(arr[j]%2 == 1 && j<n){
        j++;
    }
    if(i>j){
        temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
 
        temp = i;
        i = j;
        j = temp;
    }

  此时,有种特殊的情况,就是数组元素中全是偶数,或者全是奇数,显然就不需要进行其他的操作了。

 while(arr[i]%2 == 0 && i<n){
        i++;
        flag = 1;
    }
    int j=0;
    while(arr[j]%2 == 1 && j<n){
        j++;
    }
    if(i==n || j == n){//新添加的代码在这里
        //printf("纯\n");
        return ;
    }
    if(i>j){
        temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
 
        temp = i;
        i = j;
        j = temp;
    }

  然后到了关键的步骤,找到第一个奇数i,和第一个偶数j后,继续寻找第二个奇数i‘,然后把i‘到j的元素向后移,把i‘放到j的位置上。模仿直接插入排序。

第一步,寻找第一个奇数和第一个偶数

 

 

然后找到第二个奇数

把奇数拿出来,i到j向后移动,再把i放回去

接着进入下一次循环,再次寻找下一个奇数和偶数

此时判断条件退出。

 

 

 

while(i<n-1 && j<n-1){
        i++;
        while(arr[i]%2 == 0 && i<n){
            i++;
        }
        if(i == n){
            return ;
        }
        temp = arr[i];
        int k;
        for(k=i;k>j;k--){
            arr[k] = arr[k-1];
        }
        arr[j] = temp;
        while(j<n && arr[j]%2 == 1){
            j++;
        }
    }

  循环上面代码,最终就会保证数据的输出。  

  另外一种特殊的情况,如果数组是 1 2 3 4 5,那么我们找到第一个奇数1和第一个偶数2,这是正常现象。但是如果是1 3 5 6 7,我们找到第一个奇数1和第一个偶数6,如果继续按照上面的代码,i<j就会出错。因此我们在初始时,判断是否有连续的奇数存在,如果存在就寻找到最后一个奇数的位置。

 while(arr[i]%2 == 0 && i<n){
        i++;
        flag = 1;
    }
    if(i == 0){ //如果初始有连续的奇数存在,就寻找最后一个奇数
        while(arr[i]%2 == 1 && i<n ){
            i++;
            flag = 1;
        }
        if(flag)
            i--;
        if(arr[i]%2==0 && i==n-1)
            return ;
    }
    int j=0;
    while(arr[j]%2 == 1 && j<n){
        j++;
    }
    if(i==n || j == n){
        //printf("纯\n");
        return ;
    }
    if(i>j){
        temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
 
        temp = i;
        i = j;
        j = temp;
    }

  这个算法虽然节省了空间,但是时间复杂度要求高点。AC未能通过最后一项,最后一样测试好像是100000-40000的数据量。

代码:

#include <stdio.h>
#include <memory.h>
#define N 100000
int arr[N];
void diffoddandeven(int n);
int main(void){
    int n,i;
    while(scanf("%d",&n)!=EOF && n>0){
        memset(&arr,0,sizeof(int)*N);
        for(i=0;i<n;i++){
            scanf("%d",&arr[i]);
        }
        diffoddandeven(n);
        for(i=0;i<n-1;i++){
            printf("%d ",arr[i]);
        }
        printf("%d\n",arr[n-1]);
    }
    return 0;
}
void diffoddandeven(int n){
    int temp;
    int i=0;
    int flag = 0;
    while(arr[i]%2 == 0 && i<n){
        i++;
        flag = 1;
    }
    if(i == 0){
        while(arr[i]%2 == 1 && i<n ){
            i++;
            flag = 1;
        }
        if(flag)
            i--;
        if(arr[i]%2==0 && i==n-1)
            return ;
    }
    int j=0;
    while(arr[j]%2 == 1 && j<n){
        j++;
    }
    if(i==n || j == n){
        //printf("纯\n");
        return ;
    }
    if(i>j){
        temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
 
        temp = i;
        i = j;
        j = temp;
    }
    while(i<n-1 && j<n-1){
        i++;
        while(arr[i]%2 == 0 && i<n){
            i++;
        }
        if(i == n){
            return ;
        }
        temp = arr[i];
        int k;
        for(k=i;k>j;k--){
            arr[k] = arr[k-1];
        }
        arr[j] = temp;
        while(j<n && arr[j]%2 == 1){
            j++;
        }
    }
}
/**************************************************************
    Problem: 1516
    User: xhalo
    Language: C
    Result: Time Limit Exceed
****************************************************************/