길이 가 m 인 서열 T 를 지정 하고 길이 가 n 이 며 사전 서열 이 가장 작은 배열 을 구하 고 서열 T 가 원 하 는 배열 의 하위 서열 을 요구 합 니 다.제목 은 이러한 정렬 이 반드시 존재 하도록 보장 한다.

10264 단어 알고리즘
4. 567917. 주어진 길이 가 m 인 서열 T 는 길이 가 n 이 고 사전 서열 이 가장 작은 배열 을 구하 고 서열 T 가 원 하 는 배열 의 하위 서열 을 요구한다.제목 은 이러한 정렬 이 반드시 존재 하도록 보장 한다.입력: 52 n 은 5m 는 2442 T 시퀀스 출력 1, 3, 4, 2, 5, 567918.
4. 567917. 사고: 1 ~ n 의 숫자 에서 T 서열 에 포 함 된 숫자 를 제거 하면 후보 배열 인 arr 를 얻 고 arr 와 T 수 를 조합 하여 하나의 배열 로 만 듭 니 다
import java.util.*;
public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();  //       
        int m = sc.nextInt(); //T     
        int[] T = new int[m];
        int[] flag = new int[n];  //            
        for (int i = 0; i < m; i++) {  //  T  
            T[i] = sc.nextInt();
            flag[T[i]-1] =1;
        }
        int[] arr = new int[n-m];
        int k=0;
        //   1~n       
        for(int i=1;i<=n;i++){
            if(flag[i-1]!=1){  //  -1,   0  
                arr[k++]=i;
            }
        }
        int[] res = new int[n];
        int b=0;
        int i,j;
        for(i=0,j=0;i<k&&j<m;){
            if(arr[i]<T[j]){
                res[b++]=arr[i++]; //          ,      
            }else{
                res[b++]=T[j++];
            }
        }
        while(i<k){  //arr        
            res[b++]=arr[i++];
        }
        while(j<m){  //T        
            res[b++]=T[j++];
        }
        System.out.println(Arrays.toString(res));
    }
}

좋은 웹페이지 즐겨찾기