LetCode 문제풀이 - 전체 배열의 k번째 숫자(전체 배열 변형)

제목.

/**
 * LeetCode60 n          k   
 * The set[1,2,3,…,n]contains a total of n! unique permutations.
 By listing and labeling all of the permutations in order,
 We get the following sequence (ie, for n = 3):
 "123"
 "132"
 "213"
 "231"
 "312"
 "321"

 Given n and k, return the k th permutation sequence.
 Note: Given n will be between 1 and 9 inclusive.

     ：1 
 */

분석하다.

언뜻 보면 1~N이라는 N개의 숫자의 전체 배열

변화는 한 줄씩 줄을 서면 계수하고, k까지 계산하면 현재 줄을 서면 이 수를 출력하는 것이다

숫자가 작은 것에서 큰 것으로 나타나는 것을 어떻게 제어합니까?알고리즘 사고(귀속) 훈련: 출력 문자열 문자의 전체 배열에서 순서를 고려할 필요가 없고 실험을 통해 출력된 숫자는 완전히 작은 것에서 큰 것으로 배열되지 않는다.그래서 swap 함수를 미세하게 조정해야 한다

코드

public class PermutationSequence {

  int count;
  String result;

  public String getPermutation(int n, int k) {
    char[] arr = new char[n];
    for (int i = 0; i < n; i++)
      arr[i] = (char) ('1' + i);
    permutation(arr, 0, k);
    return result;
  }

  private void permutation(char[] arr, int index, int cc) {
    //        ，     
    //  ：              index    ，         
    if (index == arr.length) {
      count++;
      // System.out.println(String.valueOf(arr));
      if (count == cc)
        result = String.valueOf(arr);
    }
    //  index         ，            index    
    for (int k = index; k < arr.length; k++) {
      //    
      swap1(arr, index, k);
      //    index        ，            index+1           
      permutation(arr, index + 1, cc);
      //         ，        ，           ，  for          ，           
      swap2(arr, index, k);
    }
  }

  private void swap1(char[] arr, int index, int k) {
    char tmp = arr[k];
    //                
    for (int i = k; i > index; i--) {
      arr[i] = arr[i - 1];
    }
    // arr[k] = arr[index];
    arr[index] = tmp;
  }

  private void swap2(char[] arr, int index, int k) {
    char tmp = arr[index];
    //                
    for (int i = index; i < k; i++) {
      arr[i] = arr[i + 1];
    }
    arr[k] = tmp;
  }

  public static void main(String[] args) {
    Instant now = Instant.now();
    //           ： 19  
    System.out.println(new PermutationSequence().getPermutation(9,362880));
    //     987654321，362880=9！
    System.out.println("  ："+(Instant.now().toEpochMilli()-now.toEpochMilli()));
  }
}