[LeetCode] 60. Permutation Sequence

轉自LeetCode

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):

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.

<Solution>

因為是 LeetCode，所以不能傻傻的真的去排列到要求的第 K 個，一定 TLE

那要怎麼快速找到，這時候就要觀察規律了(參考資料)

用 n = 4, k = 14 說明

1234
1243
1324
1342
1423
1432
2134
2143
2314
2341
2413
2431
3124
3142  <-- k = 14
3214
3241
3412
3421
4123
4132
4213
4231
4312
4321

題目有說 n 是從 1 到 9，那先準備一個 string nums = "123456789"

從上面可以看到，第一位數字出現的累積次數為 3! = (4 - 1)! = (n - 1)! = 6

第二位數字出現的累積次數為 2! = (4 - 2)! = (n - 2)! = 2

因此可以將 k / 累積次數來知道 k 會落在哪個數字

但配合 string 的 index 從 0 開始，所以改成 (k-1) / 6，以下是分解動作

• 第一位數的 index = (k-1) / (n-1)! = (14 - 1) / 3! = 13 / 6 = 2

nums[2] = 3，這時候 3 用掉了，從 nums 拿掉 => nums = "12456789"

• k' = (k-1) % 3! = (14 - 1) % 6 = 1，第二位數的 index = k' / (n-2)! = 1 / 2! = 0

nums[0] = 1，這時候 1 用掉了，從 nums 拿掉 => nums = "2456789"

• k'' = k' % 2! = 1 % 2 = 1，第三位數的 index = k'' / (n-3)! = 1 / 1! = 1

nums[1] = 4，這時候 4 用掉了，從 nums 拿掉 => nums = "256789"

•  k''' = k'' % 1! = 1 % 1 = 0，第四位數的 index = 0 / (n-4)! =  0 / 1 = 0

nums[0] = 2，這時候 2 用掉了，從 nums 拿掉 => nums = "56789"

• 於是最後的答案就是 3142

code 如下
c++

	class Solution {
	public:
	string getPermutation(int n, int k) {
	if(n == 1) {
	return to_string(n);
	}
	string nums = "123456789";
	//> calcual that factorial
	int factorial[n+1] = {1};
	for(int i = 1; i <= n; i++) {
	factorial[i] = i * factorial[i-1];
	}
	//> find sequence
	string ans = "";
	int cnt = 1;
	--k;
	while(cnt <= n) {
	int index = k / factorial[n - cnt];
	k = k - index * factorial[n - cnt];
	ans += nums[index];
	nums.erase(index, 1);
	++cnt;
	}
	return ans;
	}
	};

view raw findPermutationSequence.cpp hosted with ❤ by GitHub

kotlin

	class Solution {
	fun getPermutation(n: Int, k: Int): String {
	return if(n == 1) {
	"1"
	} else {
	val counts = IntArray(n+1) {1}
	for(i in 1..counts.lastIndex) {
	counts[i] = i * counts[i-1]
	}
	var value = k-1
	var ans = ""
	var length = 1
	var index = 0
	val digits = mutableListOf("1","2","3","4","5","6","7","8","9")
	while(length <= n) {
	index = value / counts[n - length]
	value = value - index * counts[n - length]
	ans += digits[index]
	digits.removeAt(index)
	++length
	}
	return ans
	}
	}
	}

view raw permutation_sequence.kt hosted with ❤ by GitHub