Hard

题目描述

给你一个数组 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 <= 14
  • nums 是 [0, 1, 2, ..., n - 1] 的一个排列

提示：

  • 得分函数是循环的，所以我们总是可以设置 perm[0] = 0 来获得最小的字典序。
  • 这类似于旅行商问题。使用动态规划。
  • 使用位掩码来跟踪哪些元素已经分配给 perm。

解题思路

这道题本质上是一个旅行商问题的变种，需要使用状态压缩动态规划来解决。

核心思路：

  1. 固定起点优化：由于我们要找字典序最小的排列，可以固定 perm[0] = 0，这样既保证了字典序最小，又减少了状态空间。

  2. 状态压缩DP：使用位掩码 mask 表示已经访问过的元素集合，dp[mask][last] 表示当前访问状态为 mask，最后一个访问元素为 last 时的最小代价。

  3. 状态转移：对于当前状态 (mask, last)，尝试添加一个新的未访问元素 i，转移到状态 (mask | (1 << i), i)，代价增加 |last - nums[i]|。

  4. 路径重构：在DP过程中记录每个状态的最优前驱，用于最后重构出具体的排列路径。

  5. 字典序保证：在状态转移时，当代价相同时选择更小的元素，确保字典序最小。

整个算法的时间复杂度为 O(n² × 2ⁿ)，空间复杂度为 O(n × 2ⁿ)，适合题目给定的 n ≤ 14 的约束。

代码实现

class Solution {
public:
    vector<int> findPermutation(vector<int>& nums) {
        int n = nums.size();
        vector<vector<int>> dp(1 << n, vector<int>(n, INT_MAX));
        vector<vector<int>> parent(1 << n, vector<int>(n, -1));
        
        // 起始状态：perm[0] = 0
        dp[1][0] = 0;
        
        for (int mask = 1; mask < (1 << n); mask++) {
            for (int last = 0; last < n; last++) {
                if (!(mask & (1 << last)) || dp[mask][last] == INT_MAX) continue;
                
                for (int next = 0; next < n; next++) {
                    if (mask & (1 << next)) continue;
                    
                    int newMask = mask | (1 << next);
                    int newCost = dp[mask][last] + abs(last - nums[next]);
                    
                    if (newCost < dp[newMask][next] || 
                        (newCost == dp[newMask][next] && next < parent[newMask][next])) {
                        dp[newMask][next] = newCost;
                        parent[newMask][next] = last;
                    }
                }
            }
        }
        
        // 找到最小代价的结束状态
        int fullMask = (1 << n) - 1;
        int minCost = INT_MAX;
        int endPos = -1;
        
        for (int i = 0; i < n; i++) {
            int totalCost = dp[fullMask][i] + abs(i - nums[0]);
            if (totalCost < minCost) {
                minCost = totalCost;
                endPos = i;
            }
        }
        
        // 重构路径
        vector<int> result;
        int mask = fullMask;
        int cur = endPos;
        
        while (cur != -1) {
            result.push_back(cur);
            int prev = parent[mask][cur];
            mask ^= (1 << cur);
            cur = prev;
        }
        
        reverse(result.begin(), result.end());
        return result;
    }
};

class Solution:
    def findPermutation(self, nums: List[int]) -> List[int]:
        n = len(nums)
        dp = [[float('inf')] * n for _ in range(1 << n)]
        parent = [[-1] * n for _ in range(1 << n)]
        
        # 起始状态：perm[0] = 0
        dp[1][0] = 0
        
        for mask in range(1, 1 << n):
            for last in range(n):
                if not (mask & (1 << last)) or dp[mask][last] == float('inf'):
                    continue
                
                for next_pos in range(n):
                    if mask & (1 << next_pos):
                        continue
                    
                    new_mask = mask | (1 << next_pos)
                    new_cost = dp[mask][last] + abs(last - nums[next_pos])
                    
                    if (new_cost < dp[new_mask][next_pos] or 
                        (new_cost == dp[new_mask][next_pos] and next_pos < parent[new_mask][next_pos])):
                        dp[new_mask][next_pos] = new_cost
                        parent[new_mask][next_pos] = last
        
        # 找到最小代价的结束状态
        full_mask = (1 << n) - 1
        min_cost = float('inf')
        end_pos = -1
        
        for i in range(n):
            total_cost = dp[full_mask][i] + abs(i - nums[0])
            if total_cost < min_cost:
                min_cost = total_cost
                end_pos = i
        
        # 重构路径
        result = []
        mask = full_mask
        cur = end_pos
        
        while cur != -1:
            result.append(cur)
            prev = parent[mask][cur]
            mask ^= (1 << cur)
            cur = prev
        
        return result[::-1]

public class Solution {
    public int[] FindPermutation(int[] nums) {
        int n = nums.Length;
        int[,] dp = new int[1 << n, n];
        int[,] parent = new int[1 << n, n];
        
        // 初始化
        for (int i = 0; i < (1 << n); i++) {
            for (int j = 0; j < n; j++) {
                dp[i, j] = int.MaxValue;
                parent[i, j] = -1;
            }
        }
        
        // 起始状态：perm[0] = 0
        dp[1, 0] = 0;
        
        for (int mask = 1; mask < (1 << n); mask++) {
            for (int last = 0; last < n; last++) {
                if ((mask & (1 << last)) == 0 || dp[mask, last] == int.MaxValue) continue;
                
                for (int next = 0; next < n; next++) {
                    if ((mask & (1 << next)) != 0) continue;
                    
                    int newMask = mask | (1 << next);
                    int newCost = dp[mask, last] + Math.Abs(last - nums[next]);
                    
                    if (newCost < dp[newMask, next] || 
                        (newCost == dp[newMask, next] && next < parent[newMask, next])) {
                        dp[newMask, next] = newCost;
                        parent[newMask, next] = last;
                    }
                }
            }
        }
        
        // 找到最小代价的结束状态
        int fullMask = (1 << n) - 1;
        int minCost = int.MaxValue;
        int endPos = -1;
        
        for (int i = 0; i < n; i++) {
            int totalCost = dp[fullMask, i] + Math.Abs(i - nums[0]);
            if (totalCost < minCost) {
                minCost = totalCost;
                endPos = i;
            }
        }
        
        // 重构路径
        List<int> result = new List<int>();
        int mask = fullMask;
        int cur = endPos;
        
        while (cur != -1) {
            result.Add(cur);
            int prev = parent[mask, cur];
            mask ^= (1 << cur);
            cur = prev;
        }
        
        result.Reverse();
        return result.ToArray();
    }
}

var findPermutation = function(nums) {
    const n = nums.length;
    const memo = new Map();
    
    function dp(mask, last) {
        if (mask === (1 << n) - 1) {
            return Math.abs(last - nums[0]);
        }
        
        const key = mask * n + last;
        if (memo.has(key)) {
            return memo.get(key);
        }
        
        let minCost = Infinity;
        for (let i = 1; i < n; i++) {
            if (!(mask & (1 << i))) {
                const cost = Math.abs(last - nums[i]) + dp(mask | (1 << i), i);
                minCost = Math.min(minCost, cost);
            }
        }
        
        memo.set(key, minCost);
        return minCost;
    }
    
    function buildPath(mask, last, targetCost) {
        if (mask === (1 << n) - 1) {
            return [];
        }
        
        for (let i = 1; i < n; i++) {
            if (!(mask & (1 << i))) {
                const cost = Math.abs(last - nums[i]) + dp(mask | (1 << i), i);
                if (cost === targetCost) {
                    return [i, ...buildPath(mask | (1 << i), i, targetCost - Math.abs(last - nums[i]))];
                }
            }
        }
        return [];
    }
    
    const minCost = dp(1, 0);
    return [0, ...buildPath(1, 0, minCost)];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

项目复杂度
时间复杂度O(n² × 2ⁿ)
空间复杂度O(n × 2ⁿ)

解释：

  • 时间复杂度：有 O(2ⁿ) 个状态，每个状态有 n 个可能的最后位置，每次转移需要考虑 n 个下一个位置
  • 空间复杂度：需要存储 dp 和 parent 数组，每个都是 O(n × 2ⁿ) 的空间

相关题目