力扣00060.排列序列

发表于 分类于 阅读次数： 本文字数： 2.1k 阅读时长 ≈ 8 分钟
排列序列、递归、数学、困难

题目描述

给出集合 [1,2,3,…,n]，其所有元素共有 n! 种排列。

按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下：

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

给定 n 和 k，返回第 k 个排列。

示例 1：

输入：n = 3, k = 3
输出：”213”

示例 2：

输入：n = 4, k = 9
输出：”2314”

示例 3：

输入：n = 3, k = 1
输出：”123”

提示：

  • 1 <= n <= 9
  • 1 <= k <= n!

解决方法

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    string getPermutation(int n, int k) {
        vector<char> nums;
        for (int i = 1; i <= n; ++i) {
            nums.push_back('0' + i);
        }
        k -= 1;
        string result;
        for (int i = n; i > 0; --i) {
            int index = k / factorial(i - 1);
            k %= factorial(i - 1);
            result.push_back(nums[index]);
            nums.erase(nums.begin() + index);
        }
        return result;
    }
private:
    int factorial(int n) {
        int result = 1;
        for (int i = 2; i <= n; ++i) {
            result *= i;
        }
        return result;
    }
};

结果

执行用时 : 0 ms, 击败 100.00% 使用 C++ 的用户

内存消耗 : 7.00 MB, 击败 32.22% 使用 C++ 的用户

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public String getPermutation(int n, int k) {
        List<Integer> nums = new ArrayList<>();
        for (int i = 1; i <= n; ++i) {
            nums.add(i);
        }
        k -= 1;
        StringBuilder result = new StringBuilder();
        for (int i = n; i > 0; --i) {
            int index = k / factorial(i - 1);
            k %= factorial(i - 1);
            result.append(nums.get(index));
            nums.remove(index);
        }
        return result.toString();
    }
    private int factorial(int n) {
        int result = 1;
        for (int i = 2; i <= n; ++i) {
            result *= i;
        }
        return result;
    }
}

结果

执行用时 : 1 ms, 击败 91.08% 使用 Java 的用户

内存消耗 : 40.16 MB, 击败 34.22% 使用 Java 的用户

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution(object):
    def getPermutation(self, n, k):
        """
        :type n: int
        :type k: int
        :rtype: str
        """
        nums = [str(i) for i in range(1, n + 1)]
        result = []
        k -= 1
        for i in range(n, 0, -1):
            index, k = divmod(k, math.factorial(i - 1))
            result.append(nums.pop(index))
        return ''.join(result)

结果

执行用时 : 13 ms, 击败 78.31% 使用 Python 的用户

内存消耗 : 11.48 MB, 击败 78.31% 使用 Python 的用户

Python3

1
2
3
4
5
6
7
8
9
class Solution:
    def getPermutation(self, n: int, k: int) -> str:
        nums = [str(i) for i in range(1, n + 1)]
        result = []
        k -= 1  # Convert k to index (0-based)
        for i in range(n, 0, -1):
            index, k = divmod(k, math.factorial(i - 1))
            result.append(nums.pop(index))
        return ''.join(result)

结果

执行用时 : 36 ms, 击败 86.75% 使用 Python3 的用户

内存消耗 : 16.25 MB, 击败 61.79% 使用 Python3 的用户

C

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
int factorial(int n) {
    int result = 1;
    for (int i = 2; i <= n; ++i) {
        result *= i;
    }
    return result;
}
char* getPermutation(int n, int k) {
    char* result = (char*)malloc((n + 1) * sizeof(char));
    result[n] = '\0';
    char nums[n];
    for (int i = 0; i < n; ++i) {
        nums[i] = '0' + i + 1;
    }
    k -= 1;
    for (int i = n; i > 0; --i) {
        int index = k / factorial(i - 1);
        k %= factorial(i - 1);
        result[n - i] = nums[index];
        for (int j = index; j < i - 1; ++j) {
            nums[j] = nums[j + 1];
        }
    }
    return result;
}

结果

执行用时 : 2 ms, 击败 54.65% 使用 C 的用户

内存消耗 : 5.56 MB, 击败 70.93% 使用 C 的用户

C#

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class Solution {
    public string GetPermutation(int n, int k) {
        char[] result = new char[n];
        char[] nums = new char[n];
        for (int i = 0; i < n; i++) {
            nums[i] = (char)('0' + i + 1);
        }
        k--;
        for (int i = n; i > 0; i--) {
            int index = k / Factorial(i - 1);
            k %= Factorial(i - 1);
            result[n - i] = nums[index];
            Array.Copy(nums, index + 1, nums, index, i - index - 1);
        }
        return new string(result);
    }
    private int Factorial(int n) {
        int result = 1;
        for (int i = 2; i <= n; i++) {
            result *= i;
        }
        return result;
    }
}

结果

执行用时 : 52 ms, 击败 88.37% 使用 C# 的用户

内存消耗 : 38.84 MB, 击败 16.28% 使用 C# 的用户

JavaScript

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
 * @param {number} n
 * @param {number} k
 * @return {string}
 */
var getPermutation = function(n, k) {
    let result = [];
    let nums = [];
    for (let i = 1; i <= n; i++) {
        nums.push(i);
    }
    k--;
    for (let i = n; i > 0; i--) {
        let index = Math.floor(k / factorial(i - 1));
        k %= factorial(i - 1);
        result.push(nums[index]);
        nums.splice(index, 1);
    }
    return result.join('');
};
function factorial(n) {
    let result = 1;
    for (let i = 2; i <= n; i++) {
        result *= i;
    }
    return result;
}

结果

执行用时 : 61 ms, 击败 70.33% 使用 JavaScript 的用户

内存消耗 : 49.17 MB, 击败 53.85% 使用 JavaScript 的用户

TypeScript

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
function getPermutation(n: number, k: number): string {
    const result: number[] = [];
    const nums: number[] = [];
    for (let i = 1; i <= n; i++) {
        nums.push(i);
    }
    k--;
    for (let i = n; i > 0; i--) {
        const index = Math.floor(k / factorial(i - 1));
        k %= factorial(i - 1);
        result.push(nums[index]);
        nums.splice(index, 1);
    }
    return result.join('');
}
function factorial(n: number): number {
    let result = 1;
    for (let i = 2; i <= n; i++) {
        result *= i;
    }
    return result;
}

结果

执行用时 : 69 ms, 击败 68.75% 使用 TypeScript 的用户

内存消耗 : 51.75 MB, 击败 56.25% 使用 TypeScript 的用户

PHP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {

    /**
     * @param Integer $n
     * @param Integer $k
     * @return String
     */
    function getPermutation($n, $k) {
        $result = [];
        $nums = range(1, $n);
        $k--;
        for ($i = $n; $i > 0; $i--) {
            $index = intval($k / $this->factorial($i - 1));
            $k %= $this->factorial($i - 1);
            $result[] = $nums[$index];
            array_splice($nums, $index, 1);
        }
        return implode('', $result);
    }
    private function factorial($n) {
        $result = 1;
        for ($i = 2; $i <= $n; $i++) {
            $result *= $i;
        }
        return $result;
    }
}

结果

执行用时 : 7 ms, 击败 100.00% 使用 PHP 的用户

内存消耗 : 19.74 MB, 击败 100.00% 使用 PHP 的用户

Swift

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
    func getPermutation(_ n: Int, _ k: Int) -> String {
        if n == 1 && k == 1 { return "1" }
        var nums = [Int]()
        var remainingK = k
        for i in 1...n {
            nums.append(i)
        }
        var result = ""
        for i in stride(from: n, to: 1, by: -1) {
            let count = getCount(i)
            let count2 = count / i
            let rest = remainingK % count2
            var index = 0
            if rest == 0 {
                index = remainingK / count2 - 1
                result.append("\(nums[index])")
            } else {
                index = (remainingK - rest) / count2
                result.append("\(nums[index])")
            }
            nums.remove(at: index)
            remainingK -= count2 * index
        }
        if let num = nums.first {
            result.append("\(num)")
        }
        return result
    }
    func getCount(_ n: Int) -> Int {
        return n < 2 ? n : n * getCount(n - 1)
    }
}

结果

执行用时 : 5 ms, 击败 40.00% 使用 Swift 的用户

内存消耗 : 15.20 MB, 击败 53.33% 使用 Swift 的用户

Kotlin

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    fun getPermutation(n: Int, k: Int): String {
        if (n == 1 && k == 1) return "1"
        val nums = (1..n).toMutableList()
        var remainingK = k
        var result = ""
        for (i in n downTo 1) {
            val count = getCount(i)
            val count2 = count / i
            val rest = remainingK % count2
            var index = 0
            if (rest == 0) {
                index = remainingK / count2 - 1
                result += nums[index].toString()
            } else {
                index = (remainingK - rest) / count2
                result += nums[index].toString()
            }
            nums.removeAt(index)
            remainingK -= count2 * index
        }
        return result
    }
    private fun getCount(n: Int): Int {
        return if (n < 2) n else n * getCount(n - 1)
    }
}

结果

执行用时 : 163 ms, 击败 62.50% 使用 Kotlin 的用户

内存消耗 : 34.95 MB, 击败 37.50% 使用 Kotlin 的用户

Dart

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
  String getPermutation(int n, int k) {
    if (n == 1 && k == 1) return "1";
    List<int> nums = List.generate(n, (index) => index + 1);
    StringBuffer result = StringBuffer();
    int remainingK = k;
    for (int i = n; i > 0; i--) {
      int count = getCount(i);
      int count2 = count ~/ i;
      int rest = remainingK % count2;
      int index;
      if (rest == 0) {
        index = remainingK ~/ count2 - 1;
        result.write(nums[index]);
      } else {
        index = (remainingK - rest) ~/ count2;
        result.write(nums[index]);
      }
      nums.removeAt(index);
      remainingK -= count2 * index;
    }
    return result.toString();
  }
  int getCount(int n) => (n < 2) ? n : n * getCount(n - 1);
}

结果

执行用时 : 284 ms, 击败 100.00% 使用 Dart 的用户

内存消耗 : 144.84 MB, 击败 100.00% 使用 Dart 的用户

Go

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
func getPermutation(n int, k int) string {
	if n == 1 && k == 1 {
		return "1"
	}
	nums := make([]int, n)
	for i := 0; i < n; i++ {
		nums[i] = i + 1
	}
	var result string
	remainingK := k
	for i := n; i > 0; i-- {
		count := getCount(i)
		count2 := count / i
		rest := remainingK % count2
		var index int
		if rest == 0 {
			index = remainingK/count2 - 1
			result += strconv.Itoa(nums[index])
		} else {
			index = (remainingK - rest) / count2
			result += strconv.Itoa(nums[index])
		}
		nums = append(nums[:index], nums[index+1:]...)
		remainingK -= count2 * index
	}
	return result
}
func getCount(n int) int {
	if n < 2 {
		return n
	}
	return n * getCount(n-1)
}

结果

执行用时 : 1 ms, 击败 46.62% 使用 Go 的用户

内存消耗 : 1.91 MB, 击败 80.45% 使用 Go 的用户

Ruby

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
# @param {Integer} n
# @param {Integer} k
# @return {String}
def get_permutation(n, k)
  return '1' if n == 1 && k == 1
  nums = (1..n).to_a
  result = ''
  remaining_k = k
  (n.downto(1)).each do |i|
    count = get_count(i)
    count2 = count / i
    rest = remaining_k % count2
    index = 0
    if rest.zero?
      index = remaining_k / count2 - 1
      result += nums[index].to_s
    else
      index = (remaining_k - rest) / count2
      result += nums[index].to_s
    end
    nums.delete_at(index)
    remaining_k -= count2 * index
  end
  result
end
def get_count(n)
  n < 2 ? n : n * get_count(n - 1)
end

结果

执行用时 : 51 ms, 击败 100.00% 使用 Ruby 的用户

内存消耗 : 206.43 MB, 击败 100.00% 使用 Ruby 的用户

Scala

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
object Solution {
  def getPermutation(n: Int, k: Int): String = {
    if (n == 1 && k == 1) return "1"
    var nums = (1 to n).toList
    var remainingK = k
    var result = ""
    for (i <- n to 1 by -1) {
      val count = getCount(i)
      val count2 = count / i
      val rest = remainingK % count2
      var index = 0
      if (rest == 0) {
        index = remainingK / count2 - 1
        result += nums(index).toString
      } else {
        index = (remainingK - rest) / count2
        result += nums(index).toString
      }
      nums = nums.patch(index, Nil, 1)
      remainingK -= count2 * index
    }
    result
  }
  def getCount(n: Int): Int = {
    if (n < 2) n else n * getCount(n - 1)
  }
}

结果

执行用时 : 433 ms, 击败 100.00% 使用 Scala 的用户

内存消耗 : 51.78 MB, 击败 100.00% 使用 Scala 的用户

Rust

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
impl Solution {
    pub fn get_permutation(n: i32, k: i32) -> String {
        if n == 1 && k == 1 {
            return "1".to_string();
        }
        let mut nums: Vec<i32> = (1..=n).collect();
        let mut remaining_k = k;
        let mut result = String::new();
        for i in (1..=n).rev() {
            let count = Solution::get_count(i);
            let count2 = count / i;
            let rest = remaining_k % count2;
            let index: usize;
            if rest == 0 {
                index = (remaining_k / count2 - 1) as usize;
                result.push_str(&nums[index].to_string());
            } else {
                index = ((remaining_k - rest) / count2) as usize;
                result.push_str(&nums[index].to_string());
            }
            nums.remove(index);
            remaining_k -= count2 * index as i32;
        }
        result
    }
    fn get_count(n: i32) -> i32 {
        if n < 2 {
            n
        } else {
            n * Solution::get_count(n - 1)
        }
    }
}

结果

执行用时 : 1 ms, 击败 26.32% 使用 Rust 的用户

内存消耗 : 2.01 MB, 击败 94.74% 使用 Rust 的用户

Racket

暂时未解决

1

结果

执行用时 : ms, 击败 % 使用 Racket 的用户

内存消耗 : MB, 击败 % 使用 Racket 的用户

Erlang

暂时未解决

1

结果

执行用时 : ms, 击败 % 使用 Erlang 的用户

内存消耗 : MB, 击败 % 使用 Erlang 的用户

Elixir

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
defmodule Solution do
  @spec get_permutation(n :: integer, k :: integer) :: String.t
  def get_permutation(n, k) when n == 1 and k == 1, do: "1"
  def get_permutation(n, k) do
    get_permutation(n, k, Enum.to_list(1..n), [])
  end
  defp get_permutation(0, _, _, result), do: Enum.join(result)
  defp get_permutation(n, k, available, result) do
    count = get_count(n)
    count2 = div(count, n)
    rest = rem(k, count2)
    index =
      if rest == 0, do: div(k, count2) - 1, else: div(k - rest, count2)
    new_result = result ++ [Enum.at(available, index)]
    new_available = List.delete_at(available, index)
    get_permutation(n - 1, k - count2 * index, new_available, new_result)
  end
  defp get_count(n) when n < 2, do: n
  defp get_count(n), do: n * get_count(n - 1)
end

结果

执行用时 : 270 ms, 击败 100.00% 使用 Elixir 的用户

内存消耗 : 68.09 MB, 击败 100.00% 使用 Elixir 的用户