Icoding题解 线性表 数据调整

题干

顺序表 数据调整

已知顺序表L中的数据元素类型为int。设计算法将其调整为左右两部分，左边的元素（即排在前面的）均为奇数，右边所有元素（即排在后面的）均为偶数，并要求算法的时间复杂度为O(n),空间复杂度为O（1）。

函数原型如下：
void odd_even(SeqList *L);

相关定义如下：

1
2
3
4
5
struct _seqlist{
    ElemType elem[MAXSIZE];
    int last;
};
typedef struct _seqlist SeqList;

分析

  • 简要分析题干：

对数组中的数据进行调整，左边的元素均为奇数，右边的均为偶数。经过一次遍历即可完成目标（时间复杂度的要求），而且不另外开辟一个数组（空间复杂度的要求）。

  • 应当注意的问题：

    1. 时间复杂度和空间复杂度的要求
    2. 有关数组的操作

  • 解题思路：
    此题的关键在于满足时间复杂度和空间复杂度，两者要求我们只能对一个现存的数组进行操作。
    由相关定义可知，我们知道数组的最后一个数字的位置。因此，我们可以采用两头逼近的方法，从第0个下标和第last个下标开始，一旦发现第i个下标的数字是偶数、第last - i个下标的数字是奇数，我们就交换两个数字，直到last - i 小于或等于 i，我们直到数组遍历完成。

核心代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
void odd_even(SeqList *L) {
    //首先取得开始遍历的下标。
    int Start = 0;
    int End = L->last;
    ElemType Temp;

    //循环遍历即可
    //当Start和End重合或End与Start彼此交错，我们就知道遍历完成
    while (Start < End) {
        //发现左边下标所指是偶数，右边下标所指是奇数，就交换两者位置
        if (L->elem[Start] % 2 == 0 && L->elem[End] % 2 != 0) {
            //交换的基本操作
            Temp = L->elem[Start];
            L->elem[Start] = L->elem[End];
            L->elem[End] = Temp;
            Start++;
            End--;
        }
        //假如两边都是偶数，左边的数可能要交换，下标不动
        //右边的数字已经满足偶数在右边的条件，所以向上一个数字遍历
        else if (L->elem[Start] % 2 == 0 && L->elem[End] % 2 == 0) {
            End--;
        }
        //假如左边是奇数，右边是奇数
        //左边已经满足奇数在左边的条件，所以向下一个数字遍历
        //和上面的else if运用了一样的思想
        else if (L->elem[Start] % 2 != 0 && L->elem[End] % 2 != 0) {
            Start++;
        }
        //最后一种情况是左边为奇数，右边为偶数
        //左边向后遍历，右边向前遍历
        else {
            Start++;
            End--;
        }
    }
}

完整代码

这段代码和上面带注释的有所不同，阅者不妨思考，以下方法虽然可以通过检测，但是否过于笨拙了？这段代码和上面的代码的区别在哪？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
void odd_even(SeqList *L) {
    ElemType temp;
    SeqList* SeqList = L;
    int i = 0;
    int rear = SeqList->last;
    while(i < rear){
        if(SeqList->elem[i] % 2 != 0 && SeqList->elem[rear] % 2 == 0){
            i++;
            rear--;
        }
        else if(SeqList->elem[i] % 2 == 0 && SeqList->elem[rear] % 2 != 0){
            temp = SeqList->elem[i];
            SeqList->elem[i] = SeqList->elem[rear];
            SeqList->elem[rear] = temp;
            i++;
            rear--;
        }
        else if(SeqList->elem[i] % 2 == 0 && SeqList->elem[rear] % 2 == 0){
            temp = SeqList->elem[rear - 1];
            SeqList->elem[rear - 1] = SeqList->elem[i];
            SeqList->elem[i] = temp;
            rear--;
        }
        else{
            temp = SeqList->elem[i + 1];
            SeqList->elem[i + 1] = SeqList->elem[rear];
            SeqList->elem[rear] = temp;
            i++;
        }
    }
}
许可协议

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。