第十八 交换、反转、旋转

概述

交换（swap）、反转（reverse）、旋转（rotate）是计算机科学中最基础的三种操作。它们看似简单，却是许多经典算法的基石：

• 排序算法中的元素交换
• 字符串处理中的翻转与旋转
• 数组操作中的轮转
• 链表操作中的指针交换
• 矩阵运算中的行列变换

这三者之间存在深刻的内在联系：rotate 通过三次 reverse 实现，reverse 通过 swap 实现。理解这一关系，有助于我们以统一的视角看待各种数据变换操作。

交换（swap）操作

原理

交换操作将两个位置上的值互换。最基本的实现方式是借助一个临时变量：

$$\text{temp} = a, \quad a = b, \quad b = \text{temp}$$

也可以利用异或运算（XOR）实现无临时变量的交换（详见第十七章位运算）：

$$a = a \oplus b, \quad b = a \oplus b, \quad a = a \oplus b$$

Rust 中的 swap 方法

Rust 标准库提供了多种 swap 方法，覆盖了不同的数据结构：

1. slice.swap() – 交换切片中两个位置的元素

fn main() {
    let mut arr = [1, 2, 3, 4, 5];
    arr.swap(0, 4);
    println!("{:?}", arr); // [5, 2, 3, 4, 1]

    arr.swap(1, 3);
    println!("{:?}", arr); // [5, 4, 3, 2, 1]
}

2. Vec::swap() – 交换 Vec 中两个位置的元素

fn main() {
    let mut vec = vec!["a", "b", "c", "d"];
    vec.swap(0, 3);
    println!("{:?}", vec); // ["d", "b", "c", "a"]
}

3. std::mem::swap – 交换两个变量的值

use std::mem;

fn main() {
    let mut a = String::from("hello");
    let mut b = String::from("world");

    mem::swap(&mut a, &mut b);
    println!("a = {}, b = {}", a, b); // a = world, b = hello
}

std::mem::swap 可以交换任意类型的两个值，不仅限于数值类型。它的底层实现使用了 std::ptr::swap_nonoverlapping，对于大型结构体也能高效完成（只交换内存，不涉及深拷贝）。

异或交换（不用临时变量）

利用异或运算的自反性 $a \oplus b \oplus a = b$，可以不借助临时变量实现交换：

fn xor_swap(a: &mut i32, b: &mut i32) {
    *a ^= *b;
    *b ^= *a;
    *a ^= *b;
}

fn main() {
    let mut x = 42;
    let mut y = 99;
    println!("交换前: x = {}, y = {}", x, y);
    xor_swap(&mut x, &mut y);
    println!("交换后: x = {}, y = {}", x, y); // x = 99, y = 42
}

注意：异或交换有一个致命缺陷 – 当两个变量指向同一内存地址时，结果会变为 0。因此实际开发中应优先使用 std::mem::swap。

实战：剑指 Offer 03 – 数组中重复的数字

剑指 Offer 03. 数组中重复的数字

题目：在一个长度为 n 的数组 nums 里的所有数字都在 $0 \sim n-1$ 的范围内。找出数组中任意一个重复的数字。

思路：利用原地交换，将每个数字放到它“应该在“的位置。如果目标位置已经有相同的数字，说明找到了重复。

/// 方法：原地交换
pub fn find_repeat_number_v3(nums: Vec<i32>) -> i32 {
    let len = nums.len();
    let mut new_nums = nums;
    let mut i = 0;
    while i < len {
        let num = new_nums[i] as usize;
        if num == i {
            i += 1;
            continue;
        }
        if new_nums[num] as usize == num {
            return num as i32;
        }
        new_nums.swap(i, num);
    }

    -1
}

fn main() {
    let documents = Vec::from([2, 5, 3, 0, 5, 0]);
    let result = find_repeat_number_v3(documents);
    println!("result: {}", result); // 5 或 0
}

复杂度分析：

• 时间复杂度：$O(n)$，每个元素最多被交换一次到正确位置
• 空间复杂度：$O(1)$，原地操作，不需要额外空间

更多 swap 应用场景

选择排序中的交换

fn selection_sort(arr: &mut [i32]) {
    let n = arr.len();
    for i in 0..n {
        let mut min_idx = i;
        for j in (i + 1)..n {
            if arr[j] < arr[min_idx] {
                min_idx = j;
            }
        }
        if min_idx != i {
            arr.swap(i, min_idx);
        }
    }
}

fn main() {
    let mut arr = [64, 25, 12, 22, 11];
    selection_sort(&mut arr);
    println!("{:?}", arr); // [11, 12, 22, 25, 64]
}

快速排序中的交换

fn quick_sort(arr: &mut [i32]) {
    if arr.len() <= 1 {
        return;
    }
    let pivot = partition(arr);
    quick_sort(&mut arr[..pivot]);
    quick_sort(&mut arr[pivot + 1..]);
}

fn partition(arr: &mut [i32]) -> usize {
    let len = arr.len();
    let pivot_idx = len / 2;
    arr.swap(pivot_idx, len - 1); // 将pivot放到末尾
    let mut i = 0;
    for j in 0..len - 1 {
        if arr[j] < arr[len - 1] {
            arr.swap(i, j);
            i += 1;
        }
    }
    arr.swap(i, len - 1); // 将pivot放到正确位置
    i
}

fn main() {
    let mut arr = [3, 6, 8, 10, 1, 2, 1];
    quick_sort(&mut arr);
    println!("{:?}", arr); // [1, 1, 2, 3, 6, 8, 10]
}

反转（reverse）操作

原理

反转操作将序列中的元素顺序完全颠倒。其核心思想是双指针交换：一个指针从头部向后移动，另一个指针从尾部向前移动，逐步交换两个指针所指的元素，直到两个指针相遇。

$$[a_0, a_1, \ldots, a_{n-2}, a_{n-1}] \xrightarrow{\text{reverse}} [a_{n-1}, a_{n-2}, \ldots, a_1, a_0]$$

Rust 中的 reverse 方法

1. slice.reverse() – 原地反转切片

fn main() {
    let mut arr = [1, 2, 3, 4, 5];
    arr.reverse();
    println!("{:?}", arr); // [5, 4, 3, 2, 1]
}

2. Vec::reverse() – 原地反转 Vec

fn main() {
    let mut vec = vec!["apple", "banana", "cherry"];
    vec.reverse();
    println!("{:?}", vec); // ["cherry", "banana", "apple"]
}

3. Iterator::rev() – 反转迭代器（惰性，不修改原数据）

fn main() {
    let arr = [1, 2, 3, 4, 5];

    // rev() 返回一个反转的迭代器，不修改原数组
    for item in arr.iter().rev() {
        print!("{} ", item); // 5 4 3 2 1
    }
    println!();

    // 收集为新的 Vec
    let reversed: Vec<i32> = arr.iter().rev().copied().collect();
    println!("{:?}", reversed); // [5, 4, 3, 2, 1]
}

注意：slice.reverse() 是原地修改，而 Iterator::rev() 是惰性操作，返回一个新的迭代器视图，不会修改原始数据。

字符串反转

fn reverse_string(s: &str) -> String {
    s.chars().rev().collect()
}

fn main() {
    let original = "hello";
    let reversed = reverse_string(original);
    println!("{} -> {}", original, reversed); // hello -> olleh

    // 处理包含中文的字符串
    let chinese = "你好世界";
    let reversed_cn = reverse_string(chinese);
    println!("{} -> {}", chinese, reversed_cn); // 你好世界 -> 界世好你
}

注意：Rust 中的 String 不能直接使用 reverse() 方法（因为 String 不是切片）。需要通过 chars().rev().collect() 来实现，这样可以正确处理 UTF-8 多字节字符。

链表反转

链表反转是面试中的高频题目，体现了 swap 操作在指针操作中的应用：

#[derive(Debug)]
struct ListNode {
    val: i32,
    next: Option<Box<ListNode>>,
}

impl ListNode {
    fn new(val: i32) -> Self {
        ListNode { val, next: None }
    }
}

/// 反转链表（迭代法）
fn reverse_list(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
    let mut prev = None;
    let mut current = head;

    while let Some(mut node) = current {
        current = node.next.take(); // 暂存下一个节点
        node.next = prev;           // 反转指针
        prev = Some(node);          // 前进
    }

    prev
}

fn main() {
    // 构建链表 1 -> 2 -> 3 -> 4 -> 5
    let mut head = Some(Box::new(ListNode::new(1)));
    let mut current = head.as_mut().unwrap();
    for i in 2..=5 {
        current.next = Some(Box::new(ListNode::new(i)));
        current = current.next.as_mut().unwrap();
    }

    let reversed = reverse_list(head);
    // 输出: 5 -> 4 -> 3 -> 2 -> 1
    let mut node = &reversed;
    while let Some(n) = node {
        print!("{} -> ", n.val);
        node = &n.next;
    }
    println!("None");
}

实战：剑指 Offer 58-I – 翻转单词顺序

剑指 Offer 58 - I. 翻转单词顺序

题目：输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。

思路：先将整个字符串按空格分割为单词数组，然后反转整个数组，最后拼接。

pub fn reverse_words(s: String) -> String {
    let mut words: Vec<&str> = s.split(' ').collect();
    let mut result = String::new();
    words.reverse();
    for word in words {
        // 注意：按照" "分割，结果中空字符串为""而不是" "
        if !word.is_empty() {
            result = format!("{} {}", result, word);
        }
    }
    result.trim().to_string()
}

fn main() {
    let message = "the sky is blue";
    let result = reverse_words(message.to_string());
    println!("result: {}", result); // "blue is sky the"
}

复杂度分析：

• 时间复杂度：$O(n)$，分割和反转都是线性操作
• 空间复杂度：$O(n)$，需要存储分割后的单词数组

回文判断

利用反转操作可以方便地判断一个字符串是否为回文：

fn is_palindrome(s: &str) -> bool {
    let chars: Vec<char> = s.chars().collect();
    let n = chars.len();
    for i in 0..n / 2 {
        if chars[i] != chars[n - 1 - i] {
            return false;
        }
    }
    true
}

fn main() {
    println!("\"racecar\" 是回文: {}", is_palindrome("racecar")); // true
    println!("\"hello\" 是回文: {}", is_palindrome("hello"));     // false
    println!("\"上海自来水来自海上\" 是回文: {}", is_palindrome("上海自来水来自海上")); // true
}

整数反转

7. 整数反转

pub fn reverse(x: i32) -> i32 {
    let sign = x.signum();
    let mut n = (x as i64).abs();
    let mut result: i64 = 0;

    while n > 0 {
        result = result * 10 + n % 10;
        n /= 10;
    }

    result *= sign as i64;

    if result > i32::MAX as i64 || result < i32::MIN as i64 {
        return 0;
    }

    result as i32
}

fn main() {
    println!("{}", reverse(123));    // 321
    println!("{}", reverse(-123));   // -321
    println!("{}", reverse(120));    // 21
    println!("{}", reverse(0));      // 0
}

旋转（rotate）操作

原理

旋转操作将序列中的元素循环移动。左旋 k 位意味着每个元素向左移动 k 个位置，超出边界的元素从另一端进入。

$$[a_0, a_1, \ldots, a_{k-1}, a_k, \ldots, a_{n-1}] \xrightarrow{\text{rotate_left}(k)} [a_k, \ldots, a_{n-1}, a_0, a_1, \ldots, a_{k-1}]$$

三次翻转法

旋转可以通过三次反转来实现，这是最优雅的旋转算法。Doug Mcllroy 给出了将十元数组向上旋转 5 个位置的翻手例子：初始时掌心对着我们的脸，左手在右手上面。通过“翻转左手“、“翻转右手”、“翻转双手“三次翻转，达到模拟向左旋转 5 位的效果。

rotate(旋转) 可以通过三次 reverse 实现； reverse(反转，颠倒，翻转) 可以通过交换（swap）实现。

左旋（rotate_left）

将数组左旋 k 位，通过以下三次 reverse 实现：

（1）rotate_left(mid) 可以通过以下三次reverse实现：
reverse(0, mid);      // 翻转前半部分
reverse(mid, len);    // 翻转后半部分
reverse(0, len);      // 翻转整个数组

以 [1, 2, 3, 4, 5, 6, 7] 左旋 3 位为例：

原始:   [1, 2, 3, | 4, 5, 6, 7]
步骤1:  [3, 2, 1, | 4, 5, 6, 7]  -- reverse(0, 3)
步骤2:  [3, 2, 1, | 7, 6, 5, 4]  -- reverse(3, 7)
步骤3:  [4, 5, 6, 7, | 1, 2, 3]  -- reverse(0, 7)

右旋（rotate_right）

将数组右旋 k 位，通过以下三次 reverse 实现：

（2）rotate_right(mid) 可以通过以下三次reverse实现：
reverse(0, len);      // 翻转整个数组
reverse(0, mid);       // 翻转前半部分
reverse(mid, len);     // 翻转后半部分

Rust 中的 rotate 方法

Rust 标准库为切片提供了内置的旋转方法：

1. slice.rotate_left() – 左旋

fn main() {
    let mut arr = [1, 2, 3, 4, 5, 6, 7];
    arr.rotate_left(3);
    println!("{:?}", arr); // [4, 5, 6, 7, 1, 2, 3]

    // 旋转超过长度时自动取模
    let mut arr = [1, 2, 3, 4, 5];
    arr.rotate_left(7); // 等价于 rotate_left(2)
    println!("{:?}", arr); // [3, 4, 5, 1, 2]
}

2. slice.rotate_right() – 右旋

fn main() {
    let mut arr = [1, 2, 3, 4, 5, 6, 7];
    arr.rotate_right(3);
    println!("{:?}", arr); // [5, 6, 7, 1, 2, 3, 4]
}

注意：rotate_left(k) 等价于 rotate_right(n - k)，其中 n 为数组长度。

实战：189. 轮转数组

189. 轮转数组

题目：给定一个数组，将数组中的元素向右轮转 k 个位置。

思路：使用三次翻转法。右旋 k 位 = 先整体翻转，再分别翻转前 k 个和后 n-k 个。

pub fn rotate(nums: &mut Vec<i32>, k: i32) {
    let len = nums.len();
    if len <= 1 {
        return;
    }
    let offset = (k as usize) % len;
    if offset == 0 {
        return;
    }

    // 第一次翻转：整体翻转
    nums.reverse();

    // 第二次翻转：翻转前offset个元素
    for i in 0..offset / 2 {
        nums.swap(i, offset - i - 1);
    }

    // 第三次翻转：翻转后(len - offset)个元素
    for j in 0..(len - offset) / 2 {
        nums.swap(j + offset, len - j - 1);
    }
}

fn main() {
    let mut nums = vec![1, 2, 3, 4, 5, 6, 7];
    let k = 3;
    rotate(&mut nums, k);
    println!("result: {:?}", nums); // [5, 6, 7, 1, 2, 3, 4]
}

复杂度分析：

• 时间复杂度：$O(n)$，三次翻转总共访问每个元素约两次
• 空间复杂度：$O(1)$，原地操作

也可以直接使用 Rust 标准库方法简化：

#![allow(unused)]
fn main() {
pub fn rotate_std(nums: &mut Vec<i32>, k: i32) {
    let k = (k as usize) % nums.len();
    if k > 0 {
        nums.rotate_right(k);
    }
}
}

字符串旋转判断

判断一个字符串是否是另一个字符串旋转得到的：

fn is_rotation(s1: &str, s2: &str) -> bool {
    if s1.len() != s2.len() {
        return false;
    }
    // 将s1与自身拼接，s2如果是s1的旋转，必然是拼接后的子串
    let doubled = format!("{}{}", s1, s1);
    doubled.contains(s2)
}

fn main() {
    println!("{}", is_rotation("waterbottle", "erbottlewat")); // true
    println!("{}", is_rotation("abcde", "cdeab"));             // true
    println!("{}", is_rotation("abcde", "abced"));             // false
}

三者关系

交换、反转、旋转三者之间存在递进的包含关系：

swap（交换）
  └── reverse（反转）= 多次 swap
        └── rotate（旋转）= 三次 reverse

用代码验证这一关系：

fn main() {
    let mut arr = [1, 2, 3, 4, 5, 6, 7];

    // rotate_left(3) 等价于三次 reverse
    let mut arr2 = arr.clone();
    arr2[0..3].reverse();
    arr2[3..].reverse();
    arr2.reverse();
    println!("三次reverse: {:?}", arr2); // [4, 5, 6, 7, 1, 2, 3]

    // 使用标准库 rotate_left
    arr.rotate_left(3);
    println!("rotate_left: {:?}", arr); // [4, 5, 6, 7, 1, 2, 3]

    assert_eq!(arr, arr2);
}

理解这一关系有助于：

1. 在没有内置 rotate 的语言中，用 reverse 实现 rotate
2. 在没有内置 reverse 的语言中，用 swap 实现 reverse
3. 从更高层次理解数据变换的本质

相关问题

• 8. 字符串转整数（atoi）
• 151. 翻转字符串里的单词
• 189. 轮转数组
• 206. 反转链表
• 剑指 Offer 03. 数组中重复的数字
• 剑指 Offer 58 - I. 翻转单词顺序
• 敏感词过滤 – DFA算法(rust)

总结

三者关系：rotate = 3 * reverse，reverse = n/2 * swap

练习题

1. 反转字符串 II（LeetCode 541）：给定一个字符串 s 和一个整数 k，从字符串开头算起，每计数至 2k 个字符，就反转这 2k 字符中的前 k 个字符。

2. 旋转数组的最小值（剑指 Offer 11）：把一个数组最开始的若干个元素搬到数组的末尾，称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。

3. 链表两两交换（LeetCode 24）：给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。

4. 手动实现 reverse：不使用 slice.reverse()，仅使用 slice.swap() 实现一个切片的反转函数。

5. 字符串旋转：实现一个函数，判断字符串 s2 是否可以通过旋转 s1 得到。要求不使用字符串拼接（即不使用 s1 + s1 的技巧），而是通过逐位旋转比较。