关于数组奇偶调序问题的总结

数据结构与算法 fireling 1397℃ 0评论

数组的奇偶调序问题,主要考察的是对数组下标或者数组指针的灵活操作。“双下标”策略或者“双指针”策略是屡试不爽的一个方案。

奇偶调序无非有两大类情况:奇偶边排奇偶混排


所谓“奇偶边排”,就是奇数排在一边,偶数排在一边。比如说我们让奇数都调整到偶数的前面。

我们可以维护两个index或者两个指针,对奇数和偶数分别进行处理。

如果我们采用头指针和尾指针的方法,比如说头指针维护奇数,尾指针维护偶数:

  • 用数组的index来实现

#include <stdio.h>
void xxx(int a[], int len){
//void xxx(int *a, int len){
    int index1 = 0; //index1维护奇数
    int index2 = len-1; //index2维护偶数
    while(index1<index2){
        if (a[index1]%2 == 1)
        {
            index1++;
        }
        else if (a[index2]%2 == 0)
        {
            index2--;
        }
        else 
        {
            int temp = a[index1];
            a[index1] = a[index2];
            a[index2] = temp;
        }
    }
}
  • 用数组的指针来实现

#include <stdio.h>
void xxx(int a[], int len){
//void xxx(int *a, int len){
    int *index1 = a; //index1维护奇数
    int *index2 = a+len-1; //index2维护偶数
    while(index1<index2){
        if ((*index1)%2 == 1)
        {
            index1++;
        }
        else if ((*index2)%2 == 0)
        {
            index2--;
        }
        else 
        {
            int temp = *index1;
            *index1 = *index2;
            *index2 = temp;
        }
    }
}

如果我们采用快指针和慢指针的方法,比如说慢指针维护奇数,快指针维护偶数:

  • 用数组的index来实现

#include <stdio.h>
void xxx(int a[], int len){
//void xxx(int *a, int len){
    int index1 = 0; //index1为慢指针
    int index2 = 0; //index2为快指针
    while(index2<=len-1){
        if (a[index2]%2 == 1){
            int temp = a[index1];
            a[index1] = a[index2];
            a[index2] = temp;
            index1++;
        }
        index2++;
    }
}
  • 用数组的指针来实现

#include <stdio.h>
void xxx(int a[], int len){
//void xxx(int *a, int len){
    int *index1 = a; //index1为慢指针
    int *index2 = a; //index2为快指针
    while(index2<=a+len-1){
        if ((*index2)%2 == 1){
            int temp = *index1;
            *index1 = *index2;
            *index2 = temp;
            index1++;
        }
        index2++;
    }
}

所谓“奇偶混排”,就是奇数和偶数混合排在一起。比如说我们奇数都在偶数位,偶数都在奇数位。当然这里数组的奇数个数和偶数个数是相等的。

  • 用数组的index来实现

#include <stdio.h>
void xxx(int a[], int len){
//void xxx(int *a, int len){
    int index1 = 0; //index1维护奇数位
    int index2 = 1; //index2维护偶数位
    while(index1<=len-2 || index2<=len-1){
        if (a[index1]%2 == 1 && a[index2]%2 == 0) //第一个奇数位不是偶数,第一个偶数位不是奇数
        {
            int temp = a[index1];
            a[index1] = a[index2];
            a[index2] = temp;
            index1 += 2;
            index2 += 2;
        }
        else if (a[index1]%2 == 1) //第一个奇数位是奇数
        {
            index1 += 2;
        }
        else if (a[index2]%2 == 0) //第一个偶数位是偶数
        {
            index2 += 2;
        }
        else 
            break;
    }
}
  • 用数组的指针来实现

#include <stdio.h>
void xxx(int a[], int len){
//void xxx(int *a, int len){
    int *index1 = a; //index1维护奇数位
    int *index2 = a+1; //index2维护偶数位
    while(index1<=a+len-2 || index2<=a+len-1){
        if ((*index1)%2 == 1 && (*index2)%2 == 0) //第一个奇数位不是偶数,第一个偶数位不是奇数
        {
            int temp = *index1; //传指针
            *index1 = *index2;
            *index2 = temp;
            index1 += 2;
            index2 += 2;
        }
        else if ((*index1)%2 == 1) //第一个奇数位是奇数
        {
            index1 += 2;
        }
        else if ((*index2)%2 == 0) //第一个偶数位是偶数
        {
            index2 += 2;
        }
        else 
            break;
    }
}

对于上面的几种方案,都可以采用如下主程序进行测试:


int main(){
    int a[] = {1,2,3,4,5,6};
    int len = sizeof(a)/sizeof(int);
    for(int i = 0; i<len; i++){
        printf("%d ", a[i]);
    }
    printf("\n");
    xxx(a, len);
    for(int i = 0; i<len; i++){
        printf("%d ", a[i]);
    }
    printf("\n");
}

 

转载请注明:宁哥的小站 » 关于数组奇偶调序问题的总结

喜欢 (1)

您必须 登录 才能发表评论!