Simple Python Solution | 4ms runtime
Intuition
This problem is a "searching" problem where we find the kth lexicographical list.
If n is odd, the first number MUST be odd. If it is even, the first
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
1. This problem is a "searching" problem where we find the kth lexicographical list.
2. If n is odd, the first number MUST be odd. If it is even, the first number could be any of the n numbers.
3. After fixing the first number, we must alternate the number parities so we should know the unused numbers of each parity.

# Approach
<!-- Describe your approach to solving the problem. -->
1. Using combinatorics, we will find the number of permutations possible from list index i to the end. With this, we can check if k > number_of_possible_permutations and return early. For example:
```
n = 4
options_at_idx = [4,2,1,1] (built from the end)
options_to_end = [8,2,1,1] (suffix product of options_at_idx list)
```
2. If n is even, the first number could be even or odd. So, we find the correct number to insert at the start of the list. Once the number is found, we remove it from the corresponding list of numbers with the same parity.
3. We build the rest of the list by alternating the parities of the numbers (If n is odd, the first number must be odd so we start here). To find each number, we follow the below searching process (work through it for small cases to grasp it):
```
- The number to be inserted is at index k / rem_op[i] in the par list
- par == 1 => odd list else even list
- k is updated to be k % rem_op[i] because there are only rem_op[i]
options from the next index
```
4. Add the last number to the end of the list and return. 

# Complexity
- Time complexity:
<!-- Add your time complexity here, e.g. $$O(n)$$ -->
O(n^2) where n <= 100

- Space complexity:
<!-- Add your space complexity here, e.g. $$O(n)$$ -->
O(n) where n <= 100

# Code
```python3 []
class Solution:
    def permute(self, n: int, k: int) -> List[int]:
        # Step 1
        options = []
        for i in range(2, n+1): options.append(i//2)
        if len(options) & 1: options.append(n)
        else: options.append((n+1)//2)
        rem_op = [options[0]]
        for num in options[1:]: rem_op.append(rem_op[-1] * num)
        rem_op.reverse()
        options.reverse()
        if k > rem_op[0]: return []

        # Step 2
        res = []
        odd = [i for i in range(1, n+1, 2)]
        even = [i for i in range(2, n+1, 2)]
        i = 1 # Finding the number to insert requires the number of options left at the next position
        par = 1
        k -= 1 # zero indexing
        if i < len(options) and not n & 1:
            use = k // rem_op[i] + 1
            k %= rem_op[i]
            res.append(use)
            if use & 1:
                odd.remove(use)
                par = 0
            else: even.remove(use)
            i += 1
        
        # Step 3
        while i < len(options):
            idx = k // rem_op[i]
            k %= rem_op[i]
            if par:
                res.append(odd[idx])
                odd.remove(odd[idx])
            else:
                res.append(even[idx])
                even.remove(even[idx])
            par = not par
            i += 1
        
        # Step 4
        if par: res.append(odd[0])
        else: res.append(even[0])

        return res
```
['Python3']