算法基础算法

奇数位置元素排在偶数位置元素之前

字数统计: 1.5k字   |   阅读时长: 6分
,

摘要: 线性结构上的一种常见操作

【对数据分析、人工智能、金融科技、风控服务感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：潮汐朝夕
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

本文我们来看一个在线性结构上非常常见的操作，就是将奇数位置的元素排在偶数位置的元素之前。

首先我们考虑最简单的情况，如果这个线性结构是数组，例如 [1, 2, 3, 4]，奇数位置元素为 1, 3；偶数位置元素为 2, 4。将该奇数位置元素放到偶数位置元素之前，也就是将 1, 3 放到 2, 4 前面，[1, 3, 4, 2] 是一种可能得结果。

在此基础上，有时还会额外要求保持相对顺序，还是以 [1, 2, 3, 4] 为例子，此时 [1, 3, 4, 2] 就不行了，因为要保持相对顺序，结果只能是 [1, 3, 2, 4]。题目 932. 漂亮数组 的算法中的其中一步用到了这个操作。

同样的需求，在链表上也是有的，只是实现上稍微有一些区别。例如 1 -> 2 -> 3 -> 4，将奇数位置元素放到偶数位置元素，同时需要保持相对顺序，结果为 1 -> 3 -> 2 -> 4。题目 328. 奇偶链表 就是实现的这个操作。

下面我们解决这两个问题，其中 932 题涉及到的分治算法还有点难度，下一篇文章我们再拆解，本文仅仅把我们关心的操作实现一下，后续在拆解 932 的时候直接用即可。

$1 链表,相对位置不变

给定单链表的头节点 head ，将所有索引为奇数的节点和索引为偶数的节点分别组合在一起，然后返回重新排序的列表。

第一个节点的索引被认为是 奇数 ， 第二个节点的索引为 偶数 ，以此类推。

请注意，偶数组和奇数组内部的相对顺序应该与输入时保持一致。

你必须在 O(1) 的额外空间复杂度和 O(n) 的时间复杂度下解决这个问题。

提示:

1
2
3
n ==  链表中的节点数
0 <= n <= 1e4
-1e6 <= Node.val <= 1e6

示例 1:
输入: head = [1,2,3,4,5]
输出: [1,3,5,2,4]

示例 2:
输入: head = [2,1,3,5,6,4,7]
输出: [2,3,6,7,1,5,4]

算法：线性遍历

若链表长度小于等于 2，则返回特判的结果。当链表长度大于 2 (head -> next -> next 不为空)，在链表上走一次线性遍历，过程中调整节点的连接顺序。

指示遍历位置的指针为 iter，初始时 iter = head -> next -> next。记录一个指示当前位置是奇数位置还是偶数位置的变量 odd，再用两个指针 iter_odd 和 iter_even 分别维护已经遍历到的奇数位置元素和偶数位置元素。

若当前位置为奇数，则将 iter 节点接在 iter_odd 后面；若当前位置为偶数，则将 iter 节点接到 iter_even 后面。这样一轮遍历走完，原链表中的节点被分到了 iter_odd 和 iter_even 两个链表上，将 head_even 接到 iter_odd 后面即得调整后的链表。

代码 (C++)

$O(N)$ 时间 $O(1)$ 额外空间。

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
class Solution {
public:
    ListNode* oddEvenList(ListNode* head) {
        if(!head) 
            return nullptr;
        if(!head -> next || !head -> next -> next) 
            return head;
        ListNode *iter_odd = head, *iter_even = head -> next, *head_even = head -> next;
        int odd = 1;
        ListNode *iter = head -> next -> next;
        iter_odd -> next = nullptr;
        iter_even -> next = nullptr;
        while(iter)
        {
            if(odd == 1)
            {
                iter_odd -> next = iter;
                iter = iter -> next;
                iter_odd = iter_odd -> next;
                iter_odd -> next = nullptr;
                odd ^= 1;
            }
            else
            {
                iter_even -> next = iter;
                iter = iter -> next;
                iter_even = iter_even -> next;
                iter_even -> next = nullptr;
                odd ^= 1;
            }
        }
        iter_odd -> next = head_even;
        return head;
    }
};

$2 数组,相对位置不变

方法1：用辅助数组 $O(N)$ 时间 $O(N)$ 空间

构造长为 n 的辅助数组 tmp。

将 A[2k] 放到 tmp[k]，其中 0 <= k 且 2 * k < n。

将 A[2k + 1] 放到 tmp[(n + 1) / 2 + k]，其中 0 <= k 且 2 * k + 1 < n。

代码 (C++)

1
2
3
4
5
6
7
8
9
10
void reOrderArray(vector<int> &A)
{
    int n = A.size();
    vector<int> tmp(n, -1);
    for(int k = 0; k * 2 < n; ++k)
        tmp[k] = A[k * 2];
    for(int k = 0; k * 2 + 1 < n; ++k)
        tmp[(n + 1) / 2 + k] = A[2 * k + 1];
    A = tmp;
}

方法2：用类似冒泡排序的思想 $O(N^{2})$ 时间 $O(1)$ 空间

数组长度为 $n$，下标从 $0$ 到 $n - 1$。开始的时候，$0$ 位置肯定是正确的，所以要对 $[1, n-1]$ 范围重排。重排过程类似于冒泡排序，将 $A[1], A[2]$ 交换、$A[3], A[4]$ 交换，直至 $[1, n-1]$ 这个范围的子数组耗尽。

此后，$A[1]$ 与 $A[n-1]$ 就排好了，但 $[2, n - 2]$ 范围还没排好，于是进行新一轮的类似冒泡排序的操作，$A[2], A[3]$ 交换，$A[4], A[5]$ 交换，直至 $[2, n-2]$ 范围的子数组耗尽。

然后以此类推，直至还未排好的元素个数为 1 或 0，重排完成。下面是一个例子。

综上，重排过程就是维护双指针 $l, r$，表示当前尚未排好的子数组范围，然后一轮一轮进行操作：枚举 $i = l, l+2,\cdots$，交换 $A[i], A[i+1]$，直至 $i + 1 > r$。

每进行一轮操作，$l$ 增加 1，$r$ 减 1，进行新一轮操作，直至 $l + 1 \geq r$。

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
void reOrderArray(vector<int> &A)
{
    int n = A.size();
    int l = 1, r = n - 1;
    while(l + 1 <= r)
    {
        for(int i = l; i + 1 <= r; i += 2)
            swap(A[i], A[i + 1]);
        l++;
        r--;
    }
}
Share