【问题描述】
小蓝有一个长度为 N 的数组，初始时从左到右依次是 1, 2, 3, . . . N。
之后小蓝对这个数组进行了 M 次操作，每次操作可能是以下 2 种之一：
- 左移 x，即把 x 移动到最左边。
- 右移 x，即把 x 移动到最右边。
请你回答经过 M 次操作之后，数组从左到右每个数是多少？
【输入格式】
第一行包含 2 个整数，N 和 M。
以下 M 行每行一个操作，其中 “L x”表示左移 x，“R x”表示右移 x。
【输出格式】
输出 N 个数，代表操作后的数组。
【样例输入】
5 3
L 3
L 2
R 1
【样例输出】
2 3 4 5 1
【样例说明】
样例中的数组变化如下：
试题 C: 左移右移 4
第十三届蓝桥杯大赛软件赛决赛 Java 大学 B 组
[1, 2, 3, 4, 5] → [3, 1, 2, 4, 5] → [2, 3, 1, 4, 5] → [2, 3, 4, 5, 1]
【评测用例规模与约定】
对于 50% 的评测用例，1 ≤ N, M ≤ 10000.
对于 100% 的评测用例，1 ≤ N, M ≤ 200000, 1 ≤ x ≤ N.
解题思路
我们可以把每一个数字放入一个map集合中，自己作为key，把value当成权重值，默认为这个数字本身。每一个左移右移修改对应的权重值，最后根据权重值来排序。
可以设置一个最左边界的临界值 L=0，每进行一次左移操作，把这个元素相对的权重值改为最左临界值，再把临界值进行自减操作。
同理，设置一个最右边界的临界值R=n+1，每进行一次右移操作，把这个元素相对的权重值改为最右临界值，再把临界值进行自增操作。
Java代码（AC）
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;public class Main {static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));public static void main(String[] args) throws IOException {String[] num = br.readLine().split(" ");int n=Integer.parseInt(num[0]);int m=Integer.parseInt(num[1]);int l=0,r=n+1;HashMap<Integer,Integer> map=new HashMap<>();for (int i=1;i<=n;i++){map.put(i,i);}while (m>0){String[] s = br.readLine().split(" ");if (s[0].equals("L")){map.put(Integer.parseInt(s[1]),l--);//每次左移之后。临界值就要自减。因为后续是根据value值来排序的}else {map.put(Integer.parseInt(s[1]),r++);//每次右移之后。临界值就要自增}m--;}List<Map.Entry<Integer,Integer>> list=new ArrayList<Map.Entry<Integer,Integer>>(map.entrySet());//把map集合根据value排序Collections.sort(list, new Comparator<Map.Entry<Integer, Integer>>() {@Overridepublic int compare(Map.Entry<Integer, Integer> o1, Map.Entry<Integer, Integer> o2) {return o1.getValue()-o2.getValue();}});for (Map.Entry<Integer, Integer> mapping : list) {System.out.print(mapping.getKey()+" ");}}
}
