LeetCode 题解工作台
找出分数最低的排列
给你一个数组 nums ，它是 [0, 1, 2, ..., n - 1] 的一个 排列 。对于任意一个 [0, 1, 2, ..., n - 1] 的排列 perm ，其 分数 定义为： score(perm) = |perm[0] - nums[perm[1]]| + |perm[1] - nu…
4
题型
5
代码语言
3
相关题
当前训练重点
困难 · 状态·转移·动态规划
答案摘要
我们注意到，对于任意一个排列 ，把它循环向左移动任意次，得到的排列分数依然是相同的。由于题目要求返回字典序最小的排列，因此我们可以确定排列的第一个元素一定是 。 另外，由于题目的数据范围不超过 ，我们可以考虑使用状态压缩的方法，来表示当前排列选取的数字集合。我们用一个长度为 的二进制数 来表示当前排列选取的数字集合，其中 的第 位为 表示数字 已经被选取，为 表示数字 还未被选取。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 状态·转移·动态规划 题型思路
题目描述
给你一个数组 nums ，它是 [0, 1, 2, ..., n - 1] 的一个排列 。对于任意一个 [0, 1, 2, ..., n - 1] 的排列 perm ，其 分数 定义为：
score(perm) = |perm[0] - nums[perm[1]]| + |perm[1] - nums[perm[2]]| + ... + |perm[n - 1] - nums[perm[0]]|
返回具有 最低 分数的排列 perm 。如果存在多个满足题意且分数相等的排列，则返回其中字典序最小的一个。
示例 1：
输入：nums = [1,0,2]
输出：[0,1,2]
解释：
字典序最小且分数最低的排列是 [0,1,2]。这个排列的分数是 |0 - 0| + |1 - 2| + |2 - 1| = 2 。
示例 2：
输入：nums = [0,2,1]
输出：[0,2,1]
解释：
字典序最小且分数最低的排列是 [0,2,1]。这个排列的分数是 |0 - 1| + |2 - 2| + |1 - 0| = 2 。
提示：
2 <= n == nums.length <= 14nums是[0, 1, 2, ..., n - 1]的一个排列。
解题思路
方法一：记忆化搜索
我们注意到，对于任意一个排列 ，把它循环向左移动任意次，得到的排列分数依然是相同的。由于题目要求返回字典序最小的排列，因此我们可以确定排列的第一个元素一定是 。
另外，由于题目的数据范围不超过 ，我们可以考虑使用状态压缩的方法，来表示当前排列选取的数字集合。我们用一个长度为 的二进制数 来表示当前排列选取的数字集合，其中 的第 位为 表示数字 已经被选取，为 表示数字 还未被选取。
我们设计一个函数 ，表示当前排列选取的数字集合为 ，且最后一个选取的数字为 时，得到的排列的最小分数。初始时我们将数字 加入到排列中。
函数 的计算过程如下：
- 如果 的二进制表示中 的个数为 ，即 ，表示所有数字都已经被选取，此时返回 ；
- 否则，我们枚举下一个选取的数字 ，如果数字 还未被选取，那么我们可以将数字 加入到排列中，此时排列的分数为 ，我们需要取所有 中分数的最小值。
最后，我们利用一个函数 来构造得到最小分数的排列。我们首先将数字 加入到排列中，然后枚举下一个选取的数字 ，如果数字 还未被选取，且满足 的值等于 ，那么我们就可以将数字 加入到排列中。
时间复杂度 ，空间复杂度 。其中 为数组 的长度。
class Solution:
def findPermutation(self, nums: List[int]) -> List[int]:
@cache
def dfs(mask: int, pre: int) -> int:
if mask == (1 << n) - 1:
return abs(pre - nums[0])
res = inf
for cur in range(1, n):
if mask >> cur & 1 ^ 1:
res = min(res, abs(pre - nums[cur]) + dfs(mask | 1 << cur, cur))
return res
def g(mask: int, pre: int):
ans.append(pre)
if mask == (1 << n) - 1:
return
res = dfs(mask, pre)
for cur in range(1, n):
if mask >> cur & 1 ^ 1:
if abs(pre - nums[cur]) + dfs(mask | 1 << cur, cur) == res:
g(mask | 1 << cur, cur)
break
n = len(nums)
ans = []
g(1, 0)
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n * 2^n) due to iterating over all subsets and transitions for each state. Space complexity is O(n * 2^n) to store the DP table, which is feasible for n <= 14. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Looking for recognition that the problem reduces to cyclic state transition DP with bitmasking.
- question_mark
Expecting the candidate to optimize for lexicographically minimal permutation by fixing perm[0].
- question_mark
Observing whether the candidate correctly implements DP transitions and reconstruction from bitmask states.
常见陷阱
外企场景- error
Failing to fix perm[0] leading to incorrect lexicographical ordering.
- error
Incorrectly updating DP states without considering the cost from previous element.
- error
Trying to generate all permutations directly, causing timeouts for n = 14.
进阶变体
外企场景- arrow_right_alt
Return only the minimum cost instead of the permutation, focusing purely on DP value computation.
- arrow_right_alt
Consider a variation with non-cyclic score, requiring handling first and last elements differently.
- arrow_right_alt
Extend to larger n using heuristic pruning instead of exact DP to explore trade-offs in performance.