9.9 重组排序

﹏ヽ暗。殇╰゛Y 2024-04-07 15:08 84阅读 0赞

**题目**：

给定一个长度为N的序列A1到AN，现在要对序列进行M次操作，
    每次操作对序列的前若干项进行升序或降序排列，求经过这M次操作后得到的序列。

输入格式：
    第一行包含两个整数N和M，1≤N，M≤105。
    第二行包含N个空格隔开的整数A1到AN，1≤Ai≤109。
    接下来M行，每行包含两个整数t和x，0≤t≤1，1≤x≤N。若t=0，
    则表示对A1到Ax进行升序排列；若t=1，则表示对A1到Ax进行降序排列。操作执行顺序与输入顺序一致。
    
    输出N个空格隔开的整数，即经过M次操作后得到的序列。
    
    输入：
    4 2
    1 2 4 3
    1 3
    0 2
    输出：
    2 4 1 3

### 思路： ###

升序：将前 x 个元素剔除令为一个新数组，将新数组 Arrays.sort排序即可；  
降序：同样排序，然后需要反转数组！这里使用双指针；

public class Main{
        
      public static void main(String[] args){
        
        Scanner in=new Scanner(System.in);
        int n=in.nextInt();
        int m=in.nextInt();
        int[] nums=new int[n];
        for(int i=0;i<n;i++){
        
            nums[i]=in.nextInt();
        }
        int[][] d=new int[m][2]; // m = 0升序， 1降序;  j 为从开头到j
        for(int i=0;i<m;i++){
        
          d[i][0]=in.nextInt();
          d[i][1]=in.nextInt();
        }
        // 开始操作
        for(int k[]: d){
        
          if(k[0]==0){
        
            int x=k[1];
            up(nums,x);//升序
          }else if(k[0]==1){
        
            int x=k[1];
            down(nums,x);//降序
          }
        }
          for(int k:nums){
        
              System.out.print(k+" ");
          }
    
      }
    
      static void up(int[] nums, int x){
         //升序，直接sort
          int[] c=new int[x];
          System.arraycopy(nums,0,c,0,x);
          Arrays.sort(c);
          System.arraycopy(c,0,nums,0,x);
      }
    
      static void down(int[] nums,int x){
         //  降序
          int[] c=new int[x];
          System.arraycopy(nums,0,c,0,x);
          Arrays.sort(c); // 先升序，再反转！
          reverse(c); // 反转了！就是降序
          System.arraycopy(c,0,nums,0,x);
      }
    
      static void reverse(int[] c){
         // 双指针反转数组
          int i=0;
          int j=c.length-1;
          while(i<j){
        
              int temp=c[i];
              c[i]=c[j];
              c[j]=temp;
              i++;
              j--;
          }
      }
    
    }