☕ Java solution
![Screenshot_1.png](https://assets.leetcode.com/users/images/121381ce-2ae6-40d4-9736-11628456e627_1740896467.3106558.png)

```java []
class Solution {
    private long INF = 1000000000000001L;
    private long[][][] memo = new long[105][105][2];
    
    public long dp(int o, int e, int req) {
        if (o == 0 && e == 0) return 1;
        if (memo[o][e][req] != -1) return memo[o][e][req];
        long res = 0;
        if (req == 1) {
            if (o == 0) res = 0;
            else {
                res = o * dp(o - 1, e, 0);
                if (res >= INF) res = INF;
            }
        } else {
            if (e == 0) res = 0;
            else {
                res = e * dp(o, e - 1, 1);
                if (res >= INF) res = INF;
            }
        }
        memo[o][e][req] = res;
        return res;
    }
    
    public int[] permute(int n, long k) {
        for (int i = 0; i < 105; i++) {
            for (int j = 0; j < 105; j++) {
                memo[i][j][0] = memo[i][j][1] = -1;
            }
        }
        
        List<Integer> odds = new ArrayList<>();
        List<Integer> evens = new ArrayList<>();
        for (int i = 1; i <= n; i++) {
            if (i % 2 == 1) odds.add(i);
            else evens.add(i);
        }
        
        int O = odds.size(), E = evens.size();
        List<Integer> ans = new ArrayList<>();
        List<Integer> all = new ArrayList<>();
        for (int i = 1; i <= n; i++) all.add(i);
        Collections.sort(all);
        
        boolean found = false;
        int req = 0;
        
        for (int candidate : all) {
            long countCandidate = 0;
            if (candidate % 2 == 1) {
                if (O <= 0) continue;
                countCandidate = dp(O - 1, E, 0);
            } else {
                if (E <= 0) continue;
                countCandidate = dp(O, E - 1, 1);
            }
            
            if (k > countCandidate) {
                k -= countCandidate;
            } else {
                ans.add(candidate);
                if (candidate % 2 == 1) {
                    odds.remove(Integer.valueOf(candidate));
                    O--;
                    req = 0;
                } else {
                    evens.remove(Integer.valueOf(candidate));
                    E--;
                    req = 1;
                }
                found = true;
                break;
            }
        }
        
        if (!found) return new int[0];
        
        for (int pos = 1; pos < n; pos++) {
            if ((req == 1 && odds.isEmpty()) || (req == 0 && evens.isEmpty())) return new int[0];
            
            List<Integer> candidates = (req == 1) ? odds : evens;
            Collections.sort(candidates);
            
            long perCount = 0;
            if (req == 1) {
                if (O <= 0) return new int[0];
                perCount = dp(O - 1, E, 0);
            } else {
                if (E <= 0) return new int[0];
                perCount = dp(O, E - 1, 1);
            }
            
            if (perCount == 0) return new int[0];
            
            int index = (int)((k - 1) / perCount);
            if (index >= candidates.size()) return new int[0];
            
            int candidate = candidates.get(index);
            ans.add(candidate);
            
            if (req == 1) {
                odds.remove(Integer.valueOf(candidate));
                O--;
                req = 0;
            } else {
                evens.remove(Integer.valueOf(candidate));
                E--;
                req = 1;
            }
            
            k -= index * perCount;
        }
        
        // Convert List<Integer> to int[]
        int[] result = new int[ans.size()];
        for (int i = 0; i < ans.size(); i++) {
            result[i] = ans.get(i);
        }
        
        return result;
    }
}
```
['Java']