Permutation Sequence (M)

題目

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 for n = 3:

1. "123"
2. "132"
3. "213"
4. "231"
5. "312"
6. "321"

Given n and k, return the kth permutation sequence.

Note:

• Given n will be between 1 and 9 inclusive.
• Given k will be between 1 and n! inclusive.

Example 1:

Input: n = 3, k = 3
Output: "213"

Example 2:

Input: n = 3, k = 3
Output: "213"

題意

按字典序輸出一個遞增序列的第k個排列，

思路

對于n個數的排列，只有當后面n-1個數完成一次全排列后，才會對第一個數進行更替，即更換周期cycle為(n-1)!，且第一個數字是按照n個數中從最小數到最大數依次更替的，令 \(count=\frac{k-1}{cycle}+1\)，則排在第一位的數字是這n個數中的第count大，將該數字加入結果序列，每次得到第一位數字后，縮小n的規模求剩下n-1個數中應當排在第一位的數，同時要更新n-1個數中要求的第k個排列 \(k=(k-1)\ \%\ cycle+1\)，

笨辦法：也可以結合 0031. Next Permutation，從遞增序列開始依次計算下一個排列，

代碼實作

Java

公式計算

class Solution {
    public String getPermutation(int n, int k) {
        StringBuilder ans = new StringBuilder();
        boolean[] used = new boolean[n];		//標記剩下的數字

        while (n >= 1) {
            // 注意n=1時實際周期為0，將其周期設為1便于合并處理
            int cycle = n == 1 ? 1 : factorial(n - 1);
            int count = (k - 1) / cycle + 1;
            
            // 找到剩余數字中的第count大，并將其加入結果序列
            for (int i = 0; i < used.length; i++) {
                if (!used[i]) {
                    if (count == 1) {
                        ans.append(i + 1);
                        used[i] = true;
                        break;
                    }
                    count--;
                }
            }
            
            // 縮小待排列序列的規模
            n--;
            k = (k - 1) % cycle + 1;
        }

        return ans.toString();
    }

    private int factorial(int n) {
        int ans = 1;
        while (n != 1) {
            ans *= n--;
        }
        return ans;
    }
}

nextPermutation

class Solution {
    public String getPermutation(int n, int k) {
        char[] a = new char[n];
        for (int i = 0; i < n; i++) {
            a[i] = (char) (i + 1 + '0');
        }
        int count = 1;
        while (count < k) {
            nextPermutation(a);
            count++;
        }
        return String.valueOf(a);
    }

    // 依照當前排列計算下一個排列
    private void nextPermutation(char[] a) {
        int i = a.length - 2;
        while (i >= 0 && a[i] >= a[i + 1]) {
            i--;
        }
        // i==-1說明整個陣列是逆序排列，已經是字典序中的最后一個排列
        if (i == -1) {
            return;
        }
        int j = a.length - 1;
        while (a[j] <= a[i]) {
            j--;
        }
        swap(a, i, j);
        reverse(a, i + 1, a.length - 1);
    }

    private void reverse(char[] a, int left, int right) {
        while (left < right) {
            swap(a, left++, right--);
        }
    }

    private void swap(char[] a, int i, int j) {
        char temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}

JavaScript

公式計算

/**
 * @param {number} n
 * @param {number} k
 * @return {string}
 */
var getPermutation = function (n, k) {
  let used = new Array(n)
  let ans = ''

  while (n > 0) {
    let cycle = n === 1 ? 1 : factorial(n - 1)
    let rank = Math.trunc((k - 1) / cycle) + 1
    let count = 0
    for (let i = 0; i < used.length; i++) {
      if (!used[i]) {
        count++
        if (count === rank) {
          ans += i + 1
          used[i] = true
          break
        }
      }
    }
    k = ((k - 1) % cycle) + 1
    n--
  }

  return ans
}

let factorial = function (n) {
  return n === 1 ? n : n * factorial(n - 1)
}

nextPermutation

/**
 * @param {number} n
 * @param {number} k
 * @return {string}
 */
var getPermutation = function (n, k) {
  let count = 1
  let arr = new Array(n).fill(0).map((v, index) => index + 1)
  while (count !== k) {
    nextPermutation(arr)
    count++
  }
  return arr.join('')
}

let nextPermutation = function (arr) {
  let i = arr.length - 2
  while (i >= 0 && arr[i] >= arr[i + 1]) {
    i--
  }
  if (i === -1) {
    return
  }
  let j = arr.length - 1
  while (arr[i] >= arr[j]) {
    j--
  }
  [arr[i], arr[j]] = [arr[j], arr[i]]
  let left = i + 1,
    right = arr.length - 1
  while (left < right) {
    [arr[left++], arr[right--]] = [arr[right], arr[left]]
  }
}

標籤：其他

上一篇：0066. Plus One (E)

下一篇：Unity音量可視化——粒子隨聲浪跳動