左移右移（JAVA）

题目：

小蓝有一个长度为 N 的数组, 初始时从左到右依次是 1,2,3,…N 。

之后小蓝对这个数组进行了 M 次操作, 每次操作可能是以下 2 种之一:

左移 x, 即把 x 移动到最左边。

右移 x, 即把 x 移动到最右边。

请你回答经过 M 次操作之后, 数组从左到右每个数是多少?

输入格式
第一行包含 2 个整数, N 和 M 。

以下 M 行每行一个操作, 其中 L表示左移 x, R 表示右移 x 。

输出格式
输出 N 个数, 代表操作后的数组。

样例输入

5 3
L 3
L 2
R 1

样例输出

2 3 4 5 1

样例说明
样例中的数组变化如下:

[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.

运行限制
最大运行时间：3s
最大运行内存: 512M

初始代码：

import java.util.Scanner;
 
public class Main {
 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N, M;
        N = sc.nextInt();
        M = sc.nextInt();         //第一行输入
        int[] arr = new int[N + 2];
        for (int i = 1; i <= N; i++) {
            arr[i] = i;              //arr数组存储每个数字对应的位置
        }
        Character key;
        Integer value;              
        for (int i = 0; i < M; i++) {
            key = sc.next().charAt(0);
            value = sc.nextInt();       //第二行输入
            if (key.toString().equals("L")) {
 
                Lexchange(arr, value, N);      //左移
            } else {
 
                Rexchange(arr, value, N);       //右移
            }
        }
        int[] R = new int[N + 1];
        for (int i = 1; i <= N; i++) {
            R[arr[i]] = i;
        }
        for (int i = 1; i <= N; i++) {
            System.out.print(R[i]+" ");
        }
 
 
    }
 
    public static void Lexchange(int[] arr, int x, int N) {
        int j = 0;
        for (int i = 1; i <= N; i++) {
            if (arr[i] < arr[x]) {
                arr[i]++;
                j++;
            }
            if (j == arr[x] - 1) {
                arr[x] = 1;
                return;
            }
        }
 
 
    }
 
    public static void Rexchange(int[] arr, int x, int N) {
        int j = 0;
        for (int i = 1; i <= N; i++) {
            if (arr[i] > arr[x]) {
                arr[i]--;
                j++;
            }
            if (j == N-arr[x]) {
                arr[x]=N;
                return;
            }
        }
 
    }
}

看到题目后想到的方法，也是基本思路吧，首先找一个arr数组存储每一个数的位置，比如arr[1]=1;就是1在1的位置。

arr数组初始arr[i]=i；每一个数都在初始位置。

左移例如L 3 那么就将arr[3]=1,在3之前的1，2的位置全部加1，依次类推。

右移例如R 3 那么就将arr[3]=N,在3之后的4，5，····，N的位置全部减一，依次类推。

最后根据记录的位置将数字输出即可。

但提交后只能通过50%的用例，其它运行超时，于是进行改进。

改进后代码：

import java.util.Scanner;
 
public class Main {
 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N, M;
        N = sc.nextInt();
        M = sc.nextInt();               //第一行输入
        int[][] arr = new int[N+1][2];   //arr二维数组存储数字与权值
        for (int i = 1; i <= N; i++) {   
            arr[i][0]=arr[i][1]=i;         //初始化arr二维数组
        }
        Character key;
        Integer value;
        int L=0,R=N+1;              //初始化左右权值
        for (int i = 0; i < M; i++) {
            key = sc.next().charAt(0);
            value = sc.nextInt();
            if (key.toString().equals("L")) {
 
                Lexchange(arr, value, L);
                L--;                             //左移并改变权值
            } else {
 
                Rexchange(arr, value, R);
                R++;                           //右移并改变权值
            }
        }
        kuaipai(arr,1,N);                      //根据权值将二维数组升序排序
  for (int i=1;i<=N;i++){
      System.out.print(arr[i][0]+" ");         //输出
  }
 
 
    }
 
    public static void Lexchange(int[][] arr, int x,int L) {
        arr[x][1]=L;
    }
 
    public static void Rexchange(int[][]arr, int x,int R) {
        arr[x][1]=R;
 
    }
    public static void kuaipai(int [][] a,int l,int r){
        if (l>=r){
            return;
        }
        int prive=a[l][1];
        int e=a[l][0];
        int b=l,c=r;
        while(b<c){
            while(a[c][1]>=prive&&b<c){
                c--;
            }
            while (a[b][1]<=prive&&b<c){
                b++;
            }
            if (b<c){
                int d=a[b][0];
                a[b][0]=a[c][0];
                a[c][0]=d;
                int tem=a[b][1];
                a[b][1]=a[c][1];
                a[c][1]=tem;
            }
        }
        a[l][1]=a[c][1];
        a[l][0]=a[c][0];
        a[c][1]=prive;
        a[c][0]=e;
        kuaipai(a,c+1,r);
        kuaipai(a,l,c-1);
    }
}

看其它解题思路时看到了权值，于是用二维数组存储数字与权值。

初始时 arr[i][0]=arr[i][1]=i;每个数的权值就是它本身。

然后因为要左移右移所以我们设置左右权值L=0，R=N+1。（该数组下标是从1——N保证没有重复）

然后左移比如L 3就将arr[3][1]=L;然后左权值L减一，依次类推。

右移比如R 3就将arr[3][1]=R;然后右权值R加一，依次类推。

操作完毕后将数组按照权值排序并输出即可。