60. Permutation Sequence

leetcode hard

#array#csharp#hard#hash-table#intervals#leetcode#string

Task

Множество [1, 2, 3, ..., n] содержит в общей сложности n! уникальных перестановок.

Списком и маркировкой всех перестановок по порядку, мы получаем следующую последовательность для n = 3:

"123"

"132"

"213"

"231"

"312"

"321"

Дано n и k, верните k-ю перестановку последовательности.

Пример:

Input: n = 3, k = 3

Output: "213"

C# solution

matched/original

public class Solution {
    public string GetPermutation(int n, int k) {
        int[] factorials = new int[n];
        List<char> nums = new List<char>() { '1' };
        factorials[0] = 1;
        for (int i = 1; i < n; ++i) {
            factorials[i] = factorials[i - 1] * i;
            nums.Add((char)(i + 1 + '0'));
        }
        k--;
        StringBuilder result = new StringBuilder();
        for (int i = n - 1; i > -1; --i) {
            int idx = k / factorials[i];
            k -= idx * factorials[i];
            result.Append(nums[idx]);
            nums.RemoveAt(idx);
        }
        return result.ToString();
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public string GetPermutation(int n, int k) {
        vector<int>& factorials = new int[n];
        List<char> nums = new List<char>() { '1' };
        factorials[0] = 1;
        for (int i = 1; i < n; ++i) {
            factorials[i] = factorials[i - 1] * i;
            nums.push_back((char)(i + 1 + '0'));
        }
        k--;
        StringBuilder result = new StringBuilder();
        for (int i = n - 1; i > -1; --i) {
            int idx = k / factorials[i];
            k -= idx * factorials[i];
            result.Append(nums[idx]);
            nums.RemoveAt(idx);
        }
        return result.ToString();
    }
}

Java solution

matched/original

class Solution {
    public String getPermutation(int n, int k) {
        int[] factorials = new int[n];
        List<Integer> nums = new ArrayList() {{
            add(1);
        }};
        
        factorials[0] = 1;
        for (int i = 1; i < n; ++i) {
            factorials[i] = factorials[i - 1] * i;
            nums.add(i + 1);
        }

        --k;

        StringBuilder sb = new StringBuilder();
        for (int i = n - 1; i > -1; --i) {
            int idx = k / factorials[i];
            k -= idx * factorials[i];

            sb.append(nums.get(idx));
            nums.remove(idx);
        }
        return sb.toString();
    }
}

JavaScript solution

matched/original

var getPermutation = function (n, k) {
    let factorials = new Array(n);
    let nums = ["1"];
    factorials[0] = 1;
    for (let i = 1; i < n; ++i) {
        factorials[i] = factorials[i - 1] * i;
        nums.push((i + 1).toString());
    }
    --k;
    let output = "";
    for (let i = n - 1; i > -1; --i) {
        let idx = Math.floor(k / factorials[i]);
        k -= idx * factorials[i];
        output += nums[idx];
        nums.splice(idx, 1);
    }
    return output;
};

Python solution

matched/original

class Solution:
    def getPermutation(self, n: int, k: int) -> str:
        factorials, nums = [1], ["1"]
        for i in range(1, n):
            factorials.append(factorials[i - 1] * i)
            nums.append(str(i + 1))
        k -= 1
        output = []
        for i in range(n - 1, -1, -1):
            idx = k // factorials[i]
            k -= idx * factorials[i]
            output.append(nums[idx])
            del nums[idx]
        return "".join(output)

Go solution

matched/original

func getPermutation(n int, k int) string {
    factorials := make([]int, n)
    nums := make([]string, n)
    factorials[0] = 1
    nums[0] = "1"
    for i := 1; i < n; i++ {
        factorials[i] = factorials[i-1] * i
        nums[i] = strconv.Itoa(i + 1)
    }
    k = k - 1
    var output strings.Builder
    for i := n - 1; i > -1; i-- {
        idx := k / factorials[i]
        k -= idx * factorials[i]
        output.WriteString(nums[idx])
        nums = append(nums[:idx], nums[idx+1:]...)
    }
    return output.String()
}

Explanation

Algorithm

1️⃣

Сгенерируйте входной массив nums чисел от 1 до N.

2️⃣

Вычислите все факториальные основы от 0 до (N−1)!.

3️⃣

Уменьшите k на 1, чтобы значение попало в интервал (0, N!−1).

Используйте коэффициенты факториалов для построения перестановки.

Верните строку перестановки.

😎