操作)
1. 项目概述从一道国赛题看数据结构与算法的实战结合最近在复盘蓝桥杯的历年真题特别是国赛级别的题目总能给我带来新的启发。今天想和大家深入聊聊第十三届蓝桥杯Java B组国赛的C题——“左移右移”。这道题初看题干似乎平平无奇就是操作一个序列但真正动手实现并追求ACAccepted通过所有测试用例时你会发现它巧妙地考察了选手对基础数据结构的选择、时间复杂度分析以及边界情况的处理能力远不是简单的模拟题。很多同学在练习时可能会因为使用了直观但低效的ArrayList直接进行元素移动而导致超时这正是本题设计的精妙之处。它不满足于你会写代码更要求你能在有限的时间和内存限制下选出最优的解决方案。无论是备战蓝桥杯、准备面试还是想提升自己解决实际工程中数据维护问题的能力这道题都值得细细品味。接下来我将拆解这道题的多种解法从最直接的思路到最优的AC方案并分享我在实现过程中踩过的坑和总结的技巧。2. 题目核心需求与难点解析2.1 问题重述与输入输出规范题目描述通常如下给定一个初始为[1, 2, 3, ..., n]的序列然后进行m次操作。每次操作以“L x”或“R x”的形式给出。L x: 将值为x的元素移动到序列的最左端。R x: 将值为x的元素移动到序列的最右端。在执行完所有m次操作后需要输出最终的序列。输入格式 第一行包含两个整数n和m。 接下来m行每行一个操作指令格式为“L x”或“R x”。输出格式 一行包含n个整数表示最终序列整数之间用空格隔开。数据范围根据国赛常见难度推断1 ≤ n, m ≤ 200,000 这是关键数据量很大1 ≤ x ≤ n这个数据范围是本题的核心难点所在。n和m最大可以达到2e5这意味着任何时间复杂度高于O(n log n)的算法都极有可能在判题系统的严格时间限制下超时TLE。2.2 算法复杂度陷阱与直观解法的缺陷最直观的想法是使用一个ArrayListInteger来存储序列。当遇到L x时先找到x的索引将其从列表中移除再插入到索引0的位置遇到R x时同理移除后添加到列表末尾。我们来分析一下这个操作的时间复杂度查找元素x的索引ArrayList的indexOf(x)方法是线性扫描时间复杂度为O(n)。移除指定索引的元素ArrayList.remove(index)需要将后续元素全部向前移动一位平均时间复杂度为O(n)。在头部插入元素ArrayList.add(0, element)需要将所有现有元素向后移动一位时间复杂度为O(n)。一次L操作就包含了三次O(n)的操作单次操作最坏情况就是O(n)。对于m次操作最坏总时间复杂度高达O(m * n)在n, m 200,000时计算量是4e10这个级别绝对会超时。即使我们使用HashMap来记录值到索引的映射可以O(1)时间找到索引但ArrayList在中间删除和头部插入导致的元素移动开销O(n)依然无法避免。因此直接使用基于数组的动态列表是不可行的。注意这是本题的第一个关键认知。在算法竞赛中看到1e5量级的数据O(n²)的算法基本可以直接排除。必须思考O(n log n)或O(n)的解法。3. 高效解法设计双向链表与哈希表的珠联璧合既然ArrayList的“移动”成本太高我们就需要一种能够以O(1)时间复杂度在任意已知节点旁进行插入和删除的数据结构。双向链表正是为此而生。结合哈希表快速定位节点就能完美解决这个问题。3.1 数据结构选型与设计思路我们选择自己实现一个简单的双向链表节点类并利用两个哈希表在Java中通常用数组模拟或使用HashMap来建立值到节点、节点到值的快速映射。但更常见的竞赛写法是使用数组模拟链表这样速度更快且无需处理对象开销。核心设计数组模拟双向链表我们使用三个数组l[],r[],e[]或直接用l[],r[]和下标代表值来模拟。l[i]表示值i的左邻居是谁。r[i]表示值i的右邻居是谁。我们维护两个特殊的边界节点head左哨兵索引0和tail右哨兵索引n1。初始时head右边是1tail左边是n中间元素按顺序链接。操作的本质无论是L x还是R x都可以分解为两个步骤将x从当前链表中删除这是一个标准的双向链表删除操作只需要修改x左右邻居的指针时间复杂度O(1)。将x插入到目标位置L x插入到head节点的右边。R x插入到tail节点的左边。 这也是标准的双向链表插入操作时间复杂度O(1)。这样单次操作的时间复杂度就从O(n)降为了O(1)总时间复杂度为O(n m)完全能够应对2e5的数据量。3.2 数组模拟链表的初始化与操作详解下面我们用具体的代码和步骤来拆解这个过程。为了清晰我们假设节点的值就是其下标1到n。初始化int N 200010; // 比最大n略大包含哨兵 int[] l new int[N]; int[] r new int[N]; int head 0, tail n 1; // 哨兵节点的索引 // 初始化双向链表: head - 1 - 2 - ... - n - tail for (int i 1; i n; i) { l[i] i - 1; r[i] i 1; } // 处理边界 r[head] 1; l[1] head; r[n] tail; l[tail] n;初始状态链表就像一根穿着珠子的线每个珠子值都知道自己左边和右边的珠子是谁。删除节点k的函数remove(int k)void remove(int k) { // 将k的左右邻居直接连接起来 r[l[k]] r[k]; l[r[k]] l[k]; }这个操作就像把一根绳子中间的某个结解开然后将断开的两头重新系在一起这个结节点k就脱离了绳子。在节点a的右侧插入节点k的函数insertRight(int a, int k)void insertRight(int a, int k) { // 先将k的左右指针指向正确位置 l[k] a; r[k] r[a]; // 然后更新原a的右邻居和k的新右邻居的左指针 l[r[a]] k; r[a] k; }这个操作就像在绳子上的某个结a后面打一个新结k。需要先确定新结连接的是a和a原来的下一个结然后再更新a和原下一个结的指针让它们都知道新结的存在。在节点a的左侧插入节点k的函数insertLeft(int a, int k) 原理类似也可以通过在l[a]的右侧插入k来实现所以我们通常只实现一个insertRight就够了。对应到本题操作L x: 先remove(x)再insertRight(head, x)。R x: 先remove(x)再insertLeft(tail, x)即insertRight(l[tail], x)。所有操作完成后我们从r[head]开始沿着r[]指针一直走到tail途中经过的所有节点值就是最终序列。4. 完整AC代码实现与逐行解析理解了原理我们来看完整的Java实现。我会在关键代码处添加详细注释。import java.io.*; public class Main { static int N 200010; // 数据范围上限 static int[] l new int[N]; // l[i] 表示i的左邻居 static int[] r new int[N]; // r[i] 表示i的右邻居 public static void main(String[] args) throws IOException { BufferedReader br new BufferedReader(new InputStreamReader(System.in)); PrintWriter pw new PrintWriter(new OutputStreamWriter(System.out)); String[] s br.readLine().split( ); int n Integer.parseInt(s[0]); int m Integer.parseInt(s[1]); // 1. 初始化双向链表 // 头哨兵head0尾哨兵tailn1 int head 0, tail n 1; for (int i 1; i n; i) { l[i] i - 1; r[i] i 1; } // 链接哨兵 r[head] 1; l[1] head; r[n] tail; l[tail] n; // 2. 执行m次操作 for (int i 0; i m; i) { s br.readLine().split( ); String op s[0]; int x Integer.parseInt(s[1]); // 先将x从当前位置移除 // 标准双向链表删除操作 r[l[x]] r[x]; l[r[x]] l[x]; // 根据操作类型将x插入到新位置 if (L.equals(op)) { // 插入到head右侧即最左端 insertRight(head, x); } else { // R // 插入到tail左侧即最右端 // tail的左邻居是当前最右元素在其右侧插入xx就成为新的最右 insertRight(l[tail], x); } } // 3. 输出最终序列从head的右边开始直到tail StringBuilder sb new StringBuilder(); for (int i r[head]; i ! tail; i r[i]) { sb.append(i).append( ); } pw.println(sb.toString().trim()); pw.flush(); } // 在节点a的右侧插入节点k static void insertRight(int a, int k) { // 步骤1: 设置k的左右指针 l[k] a; r[k] r[a]; // 步骤2: 更新原结构中受影响节点的指针 l[r[a]] k; r[a] k; } }代码关键点解析IO优化使用了BufferedReader和PrintWriter进行快速输入输出这是处理大数据量竞赛题的标准操作能有效避免因IO导致的超时。哨兵节点head和tail的使用简化了边界判断。在插入最左端时我们永远在head后插入在插入最右端时我们永远在tail的前一个节点后插入。这样代码逻辑统一无需判断链表是否为空。删除操作r[l[x]] r[x]; l[r[x]] l[x];这两行是双向链表删除的核心顺序可以互换。它直接让x的左右邻居互相指向从而将x“架空”并脱离链表。插入操作insertRight函数中的四行代码顺序很重要。必须先设置新节点k的指针然后再修改原有节点的指针。如果先修改r[a]就会丢失a原右邻居的信息导致插入错误。遍历输出输出时从r[head]即第一个有效节点开始沿着r[]指针向后遍历直到遇到tail哨兵停止。这种遍历方式非常高效。5. 解法变体与性能对比分析除了数组模拟双向链表这道题还有其他几种有趣的解法各有优劣。5.1 使用LinkedHashSet的取巧解法Java标准库中的LinkedHashSet内部维护了一个双向链表来记录插入顺序并且提供了O(1)时间复杂度的查找、删除和添加到末尾操作。我们可以利用其特性初始化一个包含1到n的LinkedHashSet。遇到L x先remove(x)再借助一个新的LinkedHashSet先将x加入然后加入原集合的所有元素。这相当于重建集合时间复杂度O(n)。遇到R x先remove(x)再直接add(x)。LinkedHashSet的add会将元素放在末尾时间复杂度O(1)。这种方法的缺点是L操作是O(n)的在最坏情况全是L操作下总复杂度为O(m * n)和最初的ArrayList思路一样会超时。但它代码极其简单在数据随机或L操作较少时可能侥幸通过部分测试点不推荐作为竞赛正解。5.2 记录“权重”的离线处理法这是一种非常巧妙的思想时间复杂度O((nm) log n)适合对链表操作不熟悉的同学理解。核心思想我们不真的移动元素而是给每个元素赋予一个“位置权重”。初始时元素i的权重就是i。操作处理维护一个当前可用的最小左权重L和最大右权重R。初始L 0,R n 1。遇到L x将元素x的权重设置为--LL向左移动。遇到R x将元素x的权重设置为RR向右移动。用一个数组pos[x]记录每个元素x的当前权重。最终输出所有操作结束后我们根据pos数组的值对元素1到n进行排序。权重越小的元素在最终序列中越靠左。这种方法避免了复杂的指针操作但需要一次排序复杂度是O(n log n)。由于n最大2e5O(n log n)是完全可接受的。实现时需要注意L和R可能超出int范围可以使用long或者双关键字排序先按操作批次再按初始顺序来避免。性能对比表解法数据结构时间复杂度空间复杂度优点缺点数组模拟链表 (AC推荐)数组l[], r[]O(n m)O(n)速度最快常数小逻辑清晰需要理解链表指针操作权重排序法数组pos[]O((nm) log n)O(n)思维巧妙代码易写有排序开销需注意权重溢出LinkedHashSetLinkedHashSetInteger最坏 O(m * n)O(n)利用现成集合代码简单L操作效率低无法AC暴力ArrayListArrayListIntegerO(m * n)O(n)最直观必然超时仅用于理解题意显然数组模拟双向链表的方法在时间和空间上都是最优的是竞赛中的标准答案。6. 常见错误与调试技巧实录在实际编写和调试这道题时我遇到过不少问题这里总结一下希望大家能避开这些坑。6.1 指针操作顺序错误这是实现链表时最常见的错误。以insertRight(a, k)为例错误的顺序可能导致指针丢失。// 错误示例 r[a] k; // 先改了a的右指针 l[k] a; r[k] r[a]; // 此时 r[a] 已经是k了而不是a原来的右邻居 l[r[a]] k; // 这行访问的是 l[k]逻辑完全混乱正确顺序必须是先设置新节点k的指针l[k],r[k]因为它们依赖的是原结构中的旧值然后再更新原结构中节点的指针l[r[a]],r[a]。6.2 哨兵节点初始化或使用不当如果没有正确初始化head和tail与第一个、最后一个节点的关系或者在遍历输出时错误地包含了哨兵节点都会导致结果错误或数组越界。初始化检查确保r[head] 1且l[1] head确保l[tail] n且r[n] tail。遍历检查输出循环的条件必须是i ! tail而不是i n因为tail的值是n1。6.3 对“删除后插入”的理解偏差有些同学会疑惑为什么L x操作时如果x已经在最左边了还需要先删除再插入这样做不是多此一举吗 从结果上看如果x已经在最左删除再插入到最左其相对位置不变操作是等价的。但为了代码的统一和逻辑的清晰我们不做这个特判。O(1)的删除和插入开销极小特判带来的边界条件检查可能更容易引入错误。竞赛代码讲究正确性和简洁性这种无伤大雅的冗余操作是可以接受的。6.4 输入输出效率问题这是很多Java选手的“隐形杀手”。当m200000时使用Scanner进行输入会非常慢很可能导致超时。必须使用BufferedReader读取字符串再手动分割 (split) 或解析。输出大量数据时使用PrintWriter或StringBuilder一次性构建输出字符串避免多次调用System.out.print。6.5 数组大小开小题目说n, m 200000我们的数组大小至少需要200000 2两个哨兵。通常习惯开N 200010或者300010留出一些余量防止边界情况导致的ArrayIndexOutOfBoundsException。7. 举一反三同类问题与扩展思考“左移右移”这道题的本质是维护一个序列支持快速将指定元素移动到头部或尾部。这是一个非常经典的模型在很多场景下都有应用。1. LRU缓存算法的简化版 LRU最近最少使用缓存淘汰算法需要将最近访问的节点移动到链表头部。本题的L x操作与之神似。不同的是LRU还需要在容量满时删除尾部节点并处理键值对。本题可以看作是LRU链表操作部分的核心练习。2. 订单或日志列表的最新置顶 在一些应用界面用户手动将某条信息置顶或者最新的消息需要显示在最前面。这就可以抽象为“移动到头部”的操作。如果还有“沉底”操作那就和“移动到尾部”对应。3. 如何支持移动到任意位置如果题目扩展为“将元素x移动到元素y的左边或右边”我们的链表解法依然高效。只需要先remove(x)然后找到y节点再执行insertLeft(y, x)或insertRight(y, x)即可。查找y节点如果通过值直接访问假设值唯一且范围已知依然是O(1)如果需要通过其他属性查找则可能需要配合额外的哈希表。4. 如何支持区间操作如果题目要求将一段连续的元素整体左移或右移数组模拟链表依然可以胜任但操作会稍微复杂一些需要找到区间的头尾节点然后将整个区间从原位置摘下再插入到新位置。这考察了对链表指针更复杂的操控能力。这道“左移右移”题就像一把钥匙帮你打开了高效处理动态序列问题的一扇门。掌握数组模拟链表这项技能在面对很多需要频繁插入、删除、移动的题目时你就能游刃有余不会被表面的时间复杂度吓倒。下次再看到类似“移动”、“调整顺序”的关键词不妨先想想能不能用O(1)的链表操作来解决。 蓝桥杯国赛“左移右移”题解：数组模拟双向链表O(1)操作
1. 项目概述从一道国赛题看数据结构与算法的实战结合最近在复盘蓝桥杯的历年真题特别是国赛级别的题目总能给我带来新的启发。今天想和大家深入聊聊第十三届蓝桥杯Java B组国赛的C题——“左移右移”。这道题初看题干似乎平平无奇就是操作一个序列但真正动手实现并追求ACAccepted通过所有测试用例时你会发现它巧妙地考察了选手对基础数据结构的选择、时间复杂度分析以及边界情况的处理能力远不是简单的模拟题。很多同学在练习时可能会因为使用了直观但低效的ArrayList直接进行元素移动而导致超时这正是本题设计的精妙之处。它不满足于你会写代码更要求你能在有限的时间和内存限制下选出最优的解决方案。无论是备战蓝桥杯、准备面试还是想提升自己解决实际工程中数据维护问题的能力这道题都值得细细品味。接下来我将拆解这道题的多种解法从最直接的思路到最优的AC方案并分享我在实现过程中踩过的坑和总结的技巧。2. 题目核心需求与难点解析2.1 问题重述与输入输出规范题目描述通常如下给定一个初始为[1, 2, 3, ..., n]的序列然后进行m次操作。每次操作以“L x”或“R x”的形式给出。L x: 将值为x的元素移动到序列的最左端。R x: 将值为x的元素移动到序列的最右端。在执行完所有m次操作后需要输出最终的序列。输入格式 第一行包含两个整数n和m。 接下来m行每行一个操作指令格式为“L x”或“R x”。输出格式 一行包含n个整数表示最终序列整数之间用空格隔开。数据范围根据国赛常见难度推断1 ≤ n, m ≤ 200,000 这是关键数据量很大1 ≤ x ≤ n这个数据范围是本题的核心难点所在。n和m最大可以达到2e5这意味着任何时间复杂度高于O(n log n)的算法都极有可能在判题系统的严格时间限制下超时TLE。2.2 算法复杂度陷阱与直观解法的缺陷最直观的想法是使用一个ArrayListInteger来存储序列。当遇到L x时先找到x的索引将其从列表中移除再插入到索引0的位置遇到R x时同理移除后添加到列表末尾。我们来分析一下这个操作的时间复杂度查找元素x的索引ArrayList的indexOf(x)方法是线性扫描时间复杂度为O(n)。移除指定索引的元素ArrayList.remove(index)需要将后续元素全部向前移动一位平均时间复杂度为O(n)。在头部插入元素ArrayList.add(0, element)需要将所有现有元素向后移动一位时间复杂度为O(n)。一次L操作就包含了三次O(n)的操作单次操作最坏情况就是O(n)。对于m次操作最坏总时间复杂度高达O(m * n)在n, m 200,000时计算量是4e10这个级别绝对会超时。即使我们使用HashMap来记录值到索引的映射可以O(1)时间找到索引但ArrayList在中间删除和头部插入导致的元素移动开销O(n)依然无法避免。因此直接使用基于数组的动态列表是不可行的。注意这是本题的第一个关键认知。在算法竞赛中看到1e5量级的数据O(n²)的算法基本可以直接排除。必须思考O(n log n)或O(n)的解法。3. 高效解法设计双向链表与哈希表的珠联璧合既然ArrayList的“移动”成本太高我们就需要一种能够以O(1)时间复杂度在任意已知节点旁进行插入和删除的数据结构。双向链表正是为此而生。结合哈希表快速定位节点就能完美解决这个问题。3.1 数据结构选型与设计思路我们选择自己实现一个简单的双向链表节点类并利用两个哈希表在Java中通常用数组模拟或使用HashMap来建立值到节点、节点到值的快速映射。但更常见的竞赛写法是使用数组模拟链表这样速度更快且无需处理对象开销。核心设计数组模拟双向链表我们使用三个数组l[],r[],e[]或直接用l[],r[]和下标代表值来模拟。l[i]表示值i的左邻居是谁。r[i]表示值i的右邻居是谁。我们维护两个特殊的边界节点head左哨兵索引0和tail右哨兵索引n1。初始时head右边是1tail左边是n中间元素按顺序链接。操作的本质无论是L x还是R x都可以分解为两个步骤将x从当前链表中删除这是一个标准的双向链表删除操作只需要修改x左右邻居的指针时间复杂度O(1)。将x插入到目标位置L x插入到head节点的右边。R x插入到tail节点的左边。 这也是标准的双向链表插入操作时间复杂度O(1)。这样单次操作的时间复杂度就从O(n)降为了O(1)总时间复杂度为O(n m)完全能够应对2e5的数据量。3.2 数组模拟链表的初始化与操作详解下面我们用具体的代码和步骤来拆解这个过程。为了清晰我们假设节点的值就是其下标1到n。初始化int N 200010; // 比最大n略大包含哨兵 int[] l new int[N]; int[] r new int[N]; int head 0, tail n 1; // 哨兵节点的索引 // 初始化双向链表: head - 1 - 2 - ... - n - tail for (int i 1; i n; i) { l[i] i - 1; r[i] i 1; } // 处理边界 r[head] 1; l[1] head; r[n] tail; l[tail] n;初始状态链表就像一根穿着珠子的线每个珠子值都知道自己左边和右边的珠子是谁。删除节点k的函数remove(int k)void remove(int k) { // 将k的左右邻居直接连接起来 r[l[k]] r[k]; l[r[k]] l[k]; }这个操作就像把一根绳子中间的某个结解开然后将断开的两头重新系在一起这个结节点k就脱离了绳子。在节点a的右侧插入节点k的函数insertRight(int a, int k)void insertRight(int a, int k) { // 先将k的左右指针指向正确位置 l[k] a; r[k] r[a]; // 然后更新原a的右邻居和k的新右邻居的左指针 l[r[a]] k; r[a] k; }这个操作就像在绳子上的某个结a后面打一个新结k。需要先确定新结连接的是a和a原来的下一个结然后再更新a和原下一个结的指针让它们都知道新结的存在。在节点a的左侧插入节点k的函数insertLeft(int a, int k) 原理类似也可以通过在l[a]的右侧插入k来实现所以我们通常只实现一个insertRight就够了。对应到本题操作L x: 先remove(x)再insertRight(head, x)。R x: 先remove(x)再insertLeft(tail, x)即insertRight(l[tail], x)。所有操作完成后我们从r[head]开始沿着r[]指针一直走到tail途中经过的所有节点值就是最终序列。4. 完整AC代码实现与逐行解析理解了原理我们来看完整的Java实现。我会在关键代码处添加详细注释。import java.io.*; public class Main { static int N 200010; // 数据范围上限 static int[] l new int[N]; // l[i] 表示i的左邻居 static int[] r new int[N]; // r[i] 表示i的右邻居 public static void main(String[] args) throws IOException { BufferedReader br new BufferedReader(new InputStreamReader(System.in)); PrintWriter pw new PrintWriter(new OutputStreamWriter(System.out)); String[] s br.readLine().split( ); int n Integer.parseInt(s[0]); int m Integer.parseInt(s[1]); // 1. 初始化双向链表 // 头哨兵head0尾哨兵tailn1 int head 0, tail n 1; for (int i 1; i n; i) { l[i] i - 1; r[i] i 1; } // 链接哨兵 r[head] 1; l[1] head; r[n] tail; l[tail] n; // 2. 执行m次操作 for (int i 0; i m; i) { s br.readLine().split( ); String op s[0]; int x Integer.parseInt(s[1]); // 先将x从当前位置移除 // 标准双向链表删除操作 r[l[x]] r[x]; l[r[x]] l[x]; // 根据操作类型将x插入到新位置 if (L.equals(op)) { // 插入到head右侧即最左端 insertRight(head, x); } else { // R // 插入到tail左侧即最右端 // tail的左邻居是当前最右元素在其右侧插入xx就成为新的最右 insertRight(l[tail], x); } } // 3. 输出最终序列从head的右边开始直到tail StringBuilder sb new StringBuilder(); for (int i r[head]; i ! tail; i r[i]) { sb.append(i).append( ); } pw.println(sb.toString().trim()); pw.flush(); } // 在节点a的右侧插入节点k static void insertRight(int a, int k) { // 步骤1: 设置k的左右指针 l[k] a; r[k] r[a]; // 步骤2: 更新原结构中受影响节点的指针 l[r[a]] k; r[a] k; } }代码关键点解析IO优化使用了BufferedReader和PrintWriter进行快速输入输出这是处理大数据量竞赛题的标准操作能有效避免因IO导致的超时。哨兵节点head和tail的使用简化了边界判断。在插入最左端时我们永远在head后插入在插入最右端时我们永远在tail的前一个节点后插入。这样代码逻辑统一无需判断链表是否为空。删除操作r[l[x]] r[x]; l[r[x]] l[x];这两行是双向链表删除的核心顺序可以互换。它直接让x的左右邻居互相指向从而将x“架空”并脱离链表。插入操作insertRight函数中的四行代码顺序很重要。必须先设置新节点k的指针然后再修改原有节点的指针。如果先修改r[a]就会丢失a原右邻居的信息导致插入错误。遍历输出输出时从r[head]即第一个有效节点开始沿着r[]指针向后遍历直到遇到tail哨兵停止。这种遍历方式非常高效。5. 解法变体与性能对比分析除了数组模拟双向链表这道题还有其他几种有趣的解法各有优劣。5.1 使用LinkedHashSet的取巧解法Java标准库中的LinkedHashSet内部维护了一个双向链表来记录插入顺序并且提供了O(1)时间复杂度的查找、删除和添加到末尾操作。我们可以利用其特性初始化一个包含1到n的LinkedHashSet。遇到L x先remove(x)再借助一个新的LinkedHashSet先将x加入然后加入原集合的所有元素。这相当于重建集合时间复杂度O(n)。遇到R x先remove(x)再直接add(x)。LinkedHashSet的add会将元素放在末尾时间复杂度O(1)。这种方法的缺点是L操作是O(n)的在最坏情况全是L操作下总复杂度为O(m * n)和最初的ArrayList思路一样会超时。但它代码极其简单在数据随机或L操作较少时可能侥幸通过部分测试点不推荐作为竞赛正解。5.2 记录“权重”的离线处理法这是一种非常巧妙的思想时间复杂度O((nm) log n)适合对链表操作不熟悉的同学理解。核心思想我们不真的移动元素而是给每个元素赋予一个“位置权重”。初始时元素i的权重就是i。操作处理维护一个当前可用的最小左权重L和最大右权重R。初始L 0,R n 1。遇到L x将元素x的权重设置为--LL向左移动。遇到R x将元素x的权重设置为RR向右移动。用一个数组pos[x]记录每个元素x的当前权重。最终输出所有操作结束后我们根据pos数组的值对元素1到n进行排序。权重越小的元素在最终序列中越靠左。这种方法避免了复杂的指针操作但需要一次排序复杂度是O(n log n)。由于n最大2e5O(n log n)是完全可接受的。实现时需要注意L和R可能超出int范围可以使用long或者双关键字排序先按操作批次再按初始顺序来避免。性能对比表解法数据结构时间复杂度空间复杂度优点缺点数组模拟链表 (AC推荐)数组l[], r[]O(n m)O(n)速度最快常数小逻辑清晰需要理解链表指针操作权重排序法数组pos[]O((nm) log n)O(n)思维巧妙代码易写有排序开销需注意权重溢出LinkedHashSetLinkedHashSetInteger最坏 O(m * n)O(n)利用现成集合代码简单L操作效率低无法AC暴力ArrayListArrayListIntegerO(m * n)O(n)最直观必然超时仅用于理解题意显然数组模拟双向链表的方法在时间和空间上都是最优的是竞赛中的标准答案。6. 常见错误与调试技巧实录在实际编写和调试这道题时我遇到过不少问题这里总结一下希望大家能避开这些坑。6.1 指针操作顺序错误这是实现链表时最常见的错误。以insertRight(a, k)为例错误的顺序可能导致指针丢失。// 错误示例 r[a] k; // 先改了a的右指针 l[k] a; r[k] r[a]; // 此时 r[a] 已经是k了而不是a原来的右邻居 l[r[a]] k; // 这行访问的是 l[k]逻辑完全混乱正确顺序必须是先设置新节点k的指针l[k],r[k]因为它们依赖的是原结构中的旧值然后再更新原结构中节点的指针l[r[a]],r[a]。6.2 哨兵节点初始化或使用不当如果没有正确初始化head和tail与第一个、最后一个节点的关系或者在遍历输出时错误地包含了哨兵节点都会导致结果错误或数组越界。初始化检查确保r[head] 1且l[1] head确保l[tail] n且r[n] tail。遍历检查输出循环的条件必须是i ! tail而不是i n因为tail的值是n1。6.3 对“删除后插入”的理解偏差有些同学会疑惑为什么L x操作时如果x已经在最左边了还需要先删除再插入这样做不是多此一举吗 从结果上看如果x已经在最左删除再插入到最左其相对位置不变操作是等价的。但为了代码的统一和逻辑的清晰我们不做这个特判。O(1)的删除和插入开销极小特判带来的边界条件检查可能更容易引入错误。竞赛代码讲究正确性和简洁性这种无伤大雅的冗余操作是可以接受的。6.4 输入输出效率问题这是很多Java选手的“隐形杀手”。当m200000时使用Scanner进行输入会非常慢很可能导致超时。必须使用BufferedReader读取字符串再手动分割 (split) 或解析。输出大量数据时使用PrintWriter或StringBuilder一次性构建输出字符串避免多次调用System.out.print。6.5 数组大小开小题目说n, m 200000我们的数组大小至少需要200000 2两个哨兵。通常习惯开N 200010或者300010留出一些余量防止边界情况导致的ArrayIndexOutOfBoundsException。7. 举一反三同类问题与扩展思考“左移右移”这道题的本质是维护一个序列支持快速将指定元素移动到头部或尾部。这是一个非常经典的模型在很多场景下都有应用。1. LRU缓存算法的简化版 LRU最近最少使用缓存淘汰算法需要将最近访问的节点移动到链表头部。本题的L x操作与之神似。不同的是LRU还需要在容量满时删除尾部节点并处理键值对。本题可以看作是LRU链表操作部分的核心练习。2. 订单或日志列表的最新置顶 在一些应用界面用户手动将某条信息置顶或者最新的消息需要显示在最前面。这就可以抽象为“移动到头部”的操作。如果还有“沉底”操作那就和“移动到尾部”对应。3. 如何支持移动到任意位置如果题目扩展为“将元素x移动到元素y的左边或右边”我们的链表解法依然高效。只需要先remove(x)然后找到y节点再执行insertLeft(y, x)或insertRight(y, x)即可。查找y节点如果通过值直接访问假设值唯一且范围已知依然是O(1)如果需要通过其他属性查找则可能需要配合额外的哈希表。4. 如何支持区间操作如果题目要求将一段连续的元素整体左移或右移数组模拟链表依然可以胜任但操作会稍微复杂一些需要找到区间的头尾节点然后将整个区间从原位置摘下再插入到新位置。这考察了对链表指针更复杂的操控能力。这道“左移右移”题就像一把钥匙帮你打开了高效处理动态序列问题的一扇门。掌握数组模拟链表这项技能在面对很多需要频繁插入、删除、移动的题目时你就能游刃有余不会被表面的时间复杂度吓倒。下次再看到类似“移动”、“调整顺序”的关键词不妨先想想能不能用O(1)的链表操作来解决。