剑指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
****************************************************************/

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏黑泽君的专栏

java基础学习_基础语法(下)02_day06总结

============================================================================= ==...

611
来自专栏xingoo, 一个梦想做发明家的程序员

剑指OFFER之二维数组中的查找(九度OJ1384)

题目描述: 在一个二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组...

2267
来自专栏赵俊的Java专栏

恢复旋转排序数组

1332
来自专栏Petrichor的专栏

numpy: 常用api速查

1817
来自专栏数据结构与算法

3038 3n+1问题

3038 3n+1问题  时间限制: 1 s  空间限制: 32000 KB  题目等级 : 白银 Silver 题解 题目描述 Description 3n+...

3667
来自专栏xiaoxi666的专栏

今日头条笔试题:“最小数字*区间和”的最大值【单调栈】

  利用单调栈,从前向后和从后向前分别遍历一遍数组,得到每个元素的左边界和右边界(边界的定义即为碰到比该元素更小的即停止),最后用每个元素乘以每个元素对应的区间...

3061
来自专栏我是业余自学C/C++的

原 三对角矩阵

1513
来自专栏ACM算法日常

字符串的距离(动态规划) - leetcode 72

,因为在刷leetcode的动态规划专题。动态规划虽然定义很简单,但是对于复杂的动态规划题目,很多时候还是很棘手的。

862
来自专栏图像识别与深度学习

2018-07-02Python数组

1253
来自专栏Petrichor的专栏

numpy: np.where

Note : 不接受 list 型的参数,只接受 `ndarray 型输入。

1243

扫码关注云+社区

领取腾讯云代金券