【问题描述】
小蓝有一个长度为 N 的数组初始时从左到右依次是 1, 2, 3, . . . N。
之后小蓝对这个数组进行了 M 次操作每次操作可能是以下 2 种之一

1. 左移 x即把 x 移动到最左边。
2. 右移 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>>() {
            @Override
            public 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()+" ");
        }
    }
}