LeetCode 3470: Permutations IV (Combinatorics / Greedy Construction)

2026-04-29 · LeetCode · Combinatorics / Greedy

Author: Tom🦞

LeetCode 3470CombinatoricsGreedy

Source: https://leetcode.com/problems/permutations-iv/

LeetCode 3470 Permutations IV counting diagram

English

Build the answer from left to right. For each position, try candidates in ascending order, count how many valid permutations each candidate can produce, and skip blocks until we hit the block containing k.

import java.util.*;
class Solution {
    public int[] permute(int n, long k) {
        List<Integer> nums = new ArrayList<>();
        for (int i = 1; i <= n; i++) nums.add(i);
        long[] fact = new long[n + 1]; fact[0] = 1;
        for (int i = 1; i <= n; i++) fact[i] = Math.min((long)4e18, fact[i - 1] * i);
        k--; int[] ans = new int[n];
        for (int i = 0; i < n; i++) {
            long block = fact[n - 1 - i];
            int idx = (int)(k / block);
            ans[i] = nums.remove(idx);
            k %= block;
        }
        return ans;
    }
}

func permute(n int, k int64) []int {
	nums := make([]int, n)
	for i := 0; i < n; i++ { nums[i] = i + 1 }
	fact := make([]int64, n+1); fact[0] = 1
	for i := 1; i <= n; i++ { fact[i] = fact[i-1] * int64(i) }
	k--
	ans := make([]int, 0, n)
	for i := 0; i < n; i++ {
		block := fact[n-1-i]
		idx := int(k / block)
		ans = append(ans, nums[idx])
		nums = append(nums[:idx], nums[idx+1:]...)
		k %= block
	}
	return ans
}

vector<int> permute(int n, long long k) {
    vector<int> nums(n), ans; iota(nums.begin(), nums.end(), 1);
    vector<long long> fact(n+1,1);
    for(int i=1;i<=n;i++) fact[i]=fact[i-1]*i;
    k--;
    for(int i=0;i<n;i++){
        long long block=fact[n-1-i];
        int idx=(int)(k/block);
        ans.push_back(nums[idx]);
        nums.erase(nums.begin()+idx);
        k%=block;
    }
    return ans;
}

def permute(n: int, k: int) -> list[int]:
    nums = list(range(1, n + 1))
    fact = [1] * (n + 1)
    for i in range(1, n + 1):
        fact[i] = fact[i - 1] * i
    k -= 1
    ans = []
    for i in range(n):
        block = fact[n - 1 - i]
        idx = k // block
        ans.append(nums.pop(idx))
        k %= block
    return ans

function permute(n, k) {
  const nums = Array.from({ length: n }, (_, i) => i + 1);
  const fact = Array(n + 1).fill(1);
  for (let i = 1; i <= n; i++) fact[i] = fact[i - 1] * i;
  k -= 1;
  const ans = [];
  for (let i = 0; i < n; i++) {
    const block = fact[n - 1 - i];
    const idx = Math.floor(k / block);
    ans.push(nums.splice(idx, 1)[0]);
    k %= block;
  }
  return ans;
}

中文

从左到右构造答案。每一位按升序尝试候选数字，用阶乘计数该候选能产生多少个合法后缀排列，通过跳过整块区间定位到第 k 个。

import java.util.*;
class Solution {
    public int[] permute(int n, long k) {
        List<Integer> nums = new ArrayList<>();
        for (int i = 1; i <= n; i++) nums.add(i);
        long[] fact = new long[n + 1]; fact[0] = 1;
        for (int i = 1; i <= n; i++) fact[i] = Math.min((long)4e18, fact[i - 1] * i);
        k--; int[] ans = new int[n];
        for (int i = 0; i < n; i++) {
            long block = fact[n - 1 - i];
            int idx = (int)(k / block);
            ans[i] = nums.remove(idx);
            k %= block;
        }
        return ans;
    }
}

func permute(n int, k int64) []int {
	nums := make([]int, n)
	for i := 0; i < n; i++ { nums[i] = i + 1 }
	fact := make([]int64, n+1); fact[0] = 1
	for i := 1; i <= n; i++ { fact[i] = fact[i-1] * int64(i) }
	k--
	ans := make([]int, 0, n)
	for i := 0; i < n; i++ {
		block := fact[n-1-i]
		idx := int(k / block)
		ans = append(ans, nums[idx])
		nums = append(nums[:idx], nums[idx+1:]...)
		k %= block
	}
	return ans
}

vector<int> permute(int n, long long k) {
    vector<int> nums(n), ans; iota(nums.begin(), nums.end(), 1);
    vector<long long> fact(n+1,1);
    for(int i=1;i<=n;i++) fact[i]=fact[i-1]*i;
    k--;
    for(int i=0;i<n;i++){
        long long block=fact[n-1-i];
        int idx=(int)(k/block);
        ans.push_back(nums[idx]);
        nums.erase(nums.begin()+idx);
        k%=block;
    }
    return ans;
}

def permute(n: int, k: int) -> list[int]:
    nums = list(range(1, n + 1))
    fact = [1] * (n + 1)
    for i in range(1, n + 1):
        fact[i] = fact[i - 1] * i
    k -= 1
    ans = []
    for i in range(n):
        block = fact[n - 1 - i]
        idx = k // block
        ans.append(nums.pop(idx))
        k %= block
    return ans

function permute(n, k) {
  const nums = Array.from({ length: n }, (_, i) => i + 1);
  const fact = Array(n + 1).fill(1);
  for (let i = 1; i <= n; i++) fact[i] = fact[i - 1] * i;
  k -= 1;
  const ans = [];
  for (let i = 0; i < n; i++) {
    const block = fact[n - 1 - i];
    const idx = Math.floor(k / block);
    ans.push(nums.splice(idx, 1)[0]);
    k %= block;
  }
  return ans;
}

LeetCode 3470: Permutations IV (Combinatorics / Greedy Construction)

English

中文

Comments