AC101-反转数组指定区间¶

将序列 (a1,a2,…am,b1,b2,…bn) 转换为 (b1,b2,…bn,a1,a2,…am)

切片为AB33

代码实现¶

C
/**
 * 反转数组指定区间
 * 使用对撞指针实现原地反转
 * @param R[] 待处理数组
 * @param start 起始索引（包含）
 * @param end   结束索引（包含）
 */
void Reverse(int R[], int start, int end) {
    int i = start, j = end;

    // 对撞指针：从两端向中间移动，交换对应元素
    while (i < j) {
        int temp = R[i];  // 临时存储左边元素
        R[i] = R[j];       // 将右边元素赋值给左边
        R[j] = temp;       // 将临时存储的左边元素赋值给右边

        i++;  // 左指针右移
        j--;  // 右指针左移
    }
}

/**
 * 将序列 (a1,a2,…am,b1,b2,…bn) 转换为 (b1,b2,…bn,a1,a2,…am)
 * 利用三次反转实现原地转换
 * @param R[] 待处理数组
 * @param m   第一部分元素个数
 * @param n   第二部分元素个数
 */
void change(int R[], int m, int n) {
    // Step 1: 整体反转
    Reverse(R, 0, m + n - 1);

    // Step 2: 反转前n个元素（原来的b部分）
    Reverse(R, 0, n - 1);

    // Step 3: 反转后m个元素（原来的a部分）
    Reverse(R, n, m + n - 1);
}

算法执行过程图解¶

示例：¶

将序列 (a1,a2,a3,b1,b2) 转换为 (b1,b2,a1,a2,a3) - m = 3 （a部分有3个元素） - n = 2 （b部分有2个元素）

初始状态：¶

Text Only
1 2	`Index: 0 1 2 3 4 Array: a1 a2 a3 b1 b2`

Step 1: 整体反转¶

调用 Reverse(R, 0, 4)：

Text Only
1 2	`Original: a1 a2 a3 b1 b2 Reversed: b2 b1 a3 a2 a1`

Step 2: 反转前n个元素（原b部分）¶

调用 Reverse(R, 0, 1)：

Text Only
1 2	`Original: b2 b1 a3 a2 a1 Reversed: b1 b2 a3 a2 a1`

Step 3: 反转后m个元素（原a部分）¶

调用 Reverse(R, 2, 4)：

Text Only
1 2	`Original: b1 b2 a3 a2 a1 Reversed: b1 b2 a1 a2 a3`

最终结果：

Text Only
1 2	`Index: 0 1 2 3 4 Array: b1 b2 a1 a2 a3`

复杂度分析¶

时间复杂度：O(m+n)¶

详细分析：

整体反转：
需要交换 (m+n)/2 次
时间复杂度为 O(m+n)
前n个元素反转：
需要交换 n/2 次
时间复杂度为 O(n)
后m个元素反转：
需要交换 m/2 次
时间复杂度为 O(m)
总时间复杂度：
Text Only
1
T = O(m+n) + O(n) + O(m) = O(m+n)

空间复杂度：O(1)¶

只使用了常数个额外变量（i, j, temp）
原地操作，不需要额外的存储空间
空间复杂度为 O(1)

关键知识点延伸¶

1. 对撞指针技术¶

特点： - 使用两个指针分别从两端向中间移动 - 在每一步中交换对应的元素 - 当两指针相遇或交错时结束

应用场景： - 数组反转 - 回文判断 - 有序数组合并 - 移动零到末尾

示例：双指针反转字符串

C
void reverseString(char s[], int n) {
    int left = 0, right = n - 1;
    while (left < right) {
        char temp = s[left];
        s[left++] = s[right];
        s[right--] = temp;
    }
}

2. 三次反转法的数学原理¶

定理： 对于一个长度为 N 的数组 A，将其分为两部分 P 和 Q： - P 的长度为 m - Q 的长度为 n - N = m + n

则有：

Text Only
1	`Reverse(Reverse(P) + Reverse(Q)) = Q + P`

证明： 1. 设 P = [p1, p2, ..., pm] Q = [q1, q2, ..., qn]

Reverse(P) = [pm, ..., p2, p1] Reverse(Q) = [qn, ..., q2, q1]
Reverse(Reverse(P) + Reverse(Q)) = Reverse([pm, ..., p1, qn, ..., q1]) = [q1, q2, ..., qn, p1, p2, ..., pm] = Q + P

3. 扩展应用：循环移位¶

问题描述： 将数组中的元素向右循环移动 k 位。

解决方案： 利用三次反转法可以高效实现循环移位。

C
/**
 * 右循环移位k位
 * @param R[] 数组
 * @param n   数组长度
 * @param k   移位次数
 */
void RightShift(int R[], int n, int k) {
    k = k % n;  // 处理k大于n的情况

    // Step 1: 整体反转
    Reverse(R, 0, n - 1);

    // Step 2: 反转前k个元素
    Reverse(R, 0, k - 1);

    // Step 3: 反转后n-k个元素
    Reverse(R, k, n - 1);
}

示例： 将 [1, 2, 3, 4, 5] 向右移动2位 - Step 1: 反转整个数组 → [5, 4, 3, 2, 1] - Step 2: 反转前2个元素 → [4, 5, 3, 2, 1] - Step 3: 反转后3个元素 → [4, 5, 1, 2, 3]

4. 其他变体：分块重排¶

问题描述： 将数组重新排列为特定模式，例如： - 将 [a1, a2, ..., an, b1, b2, ..., bn] 转换为 [a1, b1, a2, b2, ..., an, bn]

解决方案： 可以使用类似的三次反转法结合其他技巧实现。

C
/**
 * 分块重排
 * @param R[] 数组
 * @param n   半段长度
 */
void Rearrange(int R[], int n) {
    // Step 1: 整体反转
    Reverse(R, 0, 2 * n - 1);

    // Step 2: 反转前半部分
    Reverse(R, 0, n - 1);

    // Step 3: 反转后半部分
    Reverse(R, n, 2 * n - 1);

    // Step 4: 逐对交换
    for (int i = 1; i < 2 * n - 1; i += 2) {
        int temp = R[i];
        R[i] = R[i + 1];
        R[i + 1] = temp;
    }
}

5. 适用场景¶

内存受限环境：需要原地操作的场景
数据重组：需要对数据进行特定顺序重组
循环移位：数组元素的循环移动
性能要求高：需要线性时间复杂度和常数空间复杂度的解决方案

算法特点总结¶

原地操作：不需要额外的存储空间
线性时间复杂度：O(m+n)，效率高
通用性强：适用于多种数据重组问题
稳定性：不改变相同元素的相对顺序
可扩展性好：可以应用于循环移位、分块重排等变体问题

记忆要点¶

"三步走"策略：整体反转 + 局部反转 + 局部反转
对撞指针：从两端向中间移动，交换元素
时间复杂度：总共遍历每个元素一次，O(m+n)
空间复杂度：只使用常数级额外空间，O(1)
适用性：特别适合内存受限的环境下进行数据重组