leetcode/maths/0060-permutation-sequence.go at main · shahzodshafizod/leetcode · GitHub

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
package maths

// https://leetcode.com/problems/permutation-sequence/

// Time: O(n)
// Space: O(n)
func getPermutation(n int, k int) string {
	nums := make([]int, n)
	factorial := 1

	for idx := 1; idx <= n; idx++ {
		nums[idx-1] = idx
		factorial *= idx
	}

	k--
	permutation := make([]byte, 0, n)

	for n > 0 {
		factorial /= n
		idx := k / factorial
		k %= factorial

		permutation = append(permutation, byte('0'+nums[idx]))
		nums = append(nums[:idx], nums[idx+1:]...)
		n--
	}

	return string(permutation)
}

// // Time: O(n + k)
// // Space: O(n)
// func getPermutation(n int, k int) string {
// 	var nums = list.New()
// 	var factorial = 1
// 	for num := 1; num <= n; num++ {
// 		nums.PushBack(num)
// 		factorial *= num
// 	}
// 	var permutation = make([]byte, 0, n)
// 	for num := n; num > 0; num-- {
// 		factorial /= num
// 		e := nums.Front()
// 		for k > factorial {
// 			e = e.Next()
// 			k -= factorial
// 		}
// 		permutation = append(permutation, byte('0'+e.Value.(int)))
// 		nums.Remove(e)
// 	}
// 	return string(permutation)
// }

// // Solved with the help of this problem:
// // 31. Next Permutation (https://leetcode.com/problems/next-permutation/)
// // Time: O(n x k)
// // Space: O(n)
// func getPermutation(n int, k int) string {
// 	var nextPermutation = func(nums []byte) {
// 		// find the starting point
// 		var pivot = n - 2
// 		for pivot >= 0 && nums[pivot] > nums[pivot+1] {
// 			pivot--
// 		}
// 		// swap pivot with the next element
// 		if pivot >= 0 {
// 			successor := n - 1
// 			for nums[successor] < nums[pivot] {
// 				successor--
// 			}
// 			nums[successor], nums[pivot] = nums[pivot], nums[successor]
// 		}
// 		// reverse the tail
// 		var left, right = pivot + 1, n - 1
// 		for left < right && nums[left] > nums[right] {
// 			nums[left], nums[right] = nums[right], nums[left]
// 			left++
// 			right--
// 		}
// 	}

// 	var nums = make([]byte, n)
// 	for idx := range nums {
// 		nums[idx] = byte('0' + idx + 1)
// 	}
// 	for k > 1 {
// 		k--
// 		nextPermutation(nums)
// 	}
// 	return string(nums)
// }