From a46ec300092c1ee8ccac629b7f335643f87662f5 Mon Sep 17 00:00:00 2001
From: Steve Lee <me@xiangyangli.com>
Date: Sat, 13 Jan 2018 05:13:14 +0800
Subject: update

---
 .../leetcode/60-permutation_sequence.c             | 33 ++++++++++++++++------
 1 file changed, 25 insertions(+), 8 deletions(-)

(limited to 'Computer_Science/leetcode/60-permutation_sequence.c')

diff --git a/Computer_Science/leetcode/60-permutation_sequence.c b/Computer_Science/leetcode/60-permutation_sequence.c
index 4eadf4c..259d00b 100644
--- a/Computer_Science/leetcode/60-permutation_sequence.c
+++ b/Computer_Science/leetcode/60-permutation_sequence.c
@@ -1,18 +1,35 @@
-char* getPermutation(int n, int k) {
-	char* result = malloc(sizeof(char) * n + 1);
+int getKth(int k, int* nums, int len)
+{
+	int result = nums[k];
+
+	for(int i = k; i < len - 1; i++)
+		nums[i] = nums[i + 1];
+
+	return result;
+}
+char* getPermutation(int n, int k)
+{
+	if(n == 0) return NULL;
+
+	char* result = malloc(sizeof(char) * (n + 1));
 	int use;
-	int used[n];
+	int nums[n];
 	int fac[n];
+	int len = n;
+
 	fac[0] = 1;
-	fac[1] = 1;
 
-	for(int i = 2; i < n; ++i) {
-		fac[i] = fac[i - 1] * n;
+	for(int i = 1; i < n; ++i) {
+		nums[i - 1] = i;
+		fac[i] = fac[i - 1] * i;
 	}
+	nums[n - 1] = n;
 
 	for(int i = 0; i < n; ++i) {
-		use = 1 + ((k - 1) / fac[n-i]);
-		k -= fac[n-i];
+		/* here k = n - 1, i.e. get 2th, index = 1 */
+		use = getKth(((k - 1) / fac[n - 1 - i]), nums, len);
+		len--;
+		k -= ((k - 1) / fac[n - 1 - i]) * fac[n - 1 - i];
 		result[i] = use + '0';
 	}
 
-- 
cgit v1.2.3