Medium

题目描述

给定一个整数 n，找到一个元素范围在 [1, n] 内的序列，该序列满足以下所有条件：

  • 整数 1 在序列中恰好出现一次。
  • 2 到 n 之间的每个整数在序列中恰好出现两次。
  • 对于 2 到 n 之间的每个整数 i，它的两次出现之间的距离恰好是 i。

序列中两个数字 a[i] 和 a[j] 之间的距离是它们下标的绝对差值，即 |j - i|。

返回字典序最大的序列。在给定约束下，保证总是存在解。

序列 a 在字典序上大于序列 b（相同长度）当且仅当在 a 和 b 第一个不同的位置上，序列 a 的数字大于序列 b 相应位置的数字。例如，[0,1,9,0] 在字典序上大于 [0,1,5,6]，因为它们第一个不同的位置是第三个数字，9 大于 5。

示例 1：

输入：n = 3
输出：[3,1,2,3,2]
解释：[2,3,2,1,3] 也是一个有效序列，但 [3,1,2,3,2] 是字典序最大的有效序列。

示例 2：

输入：n = 5
输出：[5,3,1,4,3,5,2,4,2]

提示：

  • 1 <= n <= 20

解题思路

这是一个典型的回溯问题。我们需要构造一个长度为 2*n-1 的序列，其中数字 1 出现一次，数字 2 到 n 各出现两次。

核心思路：

  1. 序列长度确定：总长度为 2n-1，因为数字 1 出现 1 次，数字 2 到 n 各出现 2 次，总共 1 + 2(n-1) = 2*n-1 个位置。

  2. 约束条件：对于数字 i (2≤i≤n)，两次出现的位置距离必须恰好为 i。

  3. 字典序最大策略：为了获得字典序最大的结果，我们应该贪心地从大到小尝试放置数字。在回溯过程中，对于每个空位置，优先尝试放置较大的数字。

  4. 回溯算法：

    • 从左到右遍历序列的每个位置
    • 对于每个空位置，从大到小尝试放置未使用完的数字
    • 对于数字 1，直接放置；对于数字 i (i≥2)，需要检查位置 pos+i 是否可用
    • 如果放置成功，继续递归；如果失败，回溯

  5. 优化细节：使用数组记录每个数字的使用次数，避免重复计算。

时间复杂度主要取决于回溯的深度和每层的分支数，在最坏情况下可能很高，但由于 n≤20 且问题保证有解，实际运行效率是可接受的。

代码实现

class Solution {
public:
    vector<int> constructDistancedSequence(int n) {
        vector<int> result(2 * n - 1, 0);
        vector<int> count(n + 1, 2);
        count[1] = 1;
        
        backtrack(result, count, n, 0);
        return result;
    }
    
private:
    bool backtrack(vector<int>& result, vector<int>& count, int n, int pos) {
        if (pos == result.size()) {
            return true;
        }
        
        if (result[pos] != 0) {
            return backtrack(result, count, n, pos + 1);
        }
        
        for (int i = n; i >= 1; i--) {
            if (count[i] == 0) continue;
            
            if (i == 1) {
                result[pos] = 1;
                count[1]--;
                if (backtrack(result, count, n, pos + 1)) {
                    return true;
                }
                result[pos] = 0;
                count[1]++;
            } else {
                if (pos + i < result.size() && result[pos + i] == 0) {
                    result[pos] = i;
                    result[pos + i] = i;
                    count[i] -= 2;
                    if (backtrack(result, count, n, pos + 1)) {
                        return true;
                    }
                    result[pos] = 0;
                    result[pos + i] = 0;
                    count[i] += 2;
                }
            }
        }
        
        return false;
    }
};

class Solution:
    def constructDistancedSequence(self, n: int) -> List[int]:
        result = [0] * (2 * n - 1)
        count = [2] * (n + 1)
        count[1] = 1
        
        def backtrack(pos):
            if pos == len(result):
                return True
            
            if result[pos] != 0:
                return backtrack(pos + 1)
            
            for i in range(n, 0, -1):
                if count[i] == 0:
                    continue
                
                if i == 1:
                    result[pos] = 1
                    count[1] -= 1
                    if backtrack(pos + 1):
                        return True
                    result[pos] = 0
                    count[1] += 1
                else:
                    if pos + i < len(result) and result[pos + i] == 0:
                        result[pos] = i
                        result[pos + i] = i
                        count[i] -= 2
                        if backtrack(pos + 1):
                            return True
                        result[pos] = 0
                        result[pos + i] = 0
                        count[i] += 2
            
            return False
        
        backtrack(0)
        return result

public class Solution {
    public int[] ConstructDistancedSequence(int n) {
        int[] result = new int[2 * n - 1];
        int[] count = new int[n + 1];
        
        for (int i = 2; i <= n; i++) {
            count[i] = 2;
        }
        count[1] = 1;
        
        Backtrack(result, count, n, 0);
        return result;
    }
    
    private bool Backtrack(int[] result, int[] count, int n, int pos) {
        if (pos == result.Length) {
            return true;
        }
        
        if (result[pos] != 0) {
            return Backtrack(result, count, n, pos + 1);
        }
        
        for (int i = n; i >= 1; i--) {
            if (count[i] == 0) continue;
            
            if (i == 1) {
                result[pos] = 1;
                count[1]--;
                if (Backtrack(result, count, n, pos + 1)) {
                    return true;
                }
                result[pos] = 0;
                count[1]++;
            } else {
                if (pos + i < result.Length && result[pos + i] == 0) {
                    result[pos] = i;
                    result[pos + i] = i;
                    count[i] -= 2;
                    if (Backtrack(result, count, n, pos + 1)) {
                        return true;
                    }
                    result[pos] = 0;
                    result[pos + i] = 0;
                    count[i] += 2;
                }
            }
        }
        
        return false;
    }
}

var constructDistancedSequence = function(n) {
    const len = 2 * n - 1;
    const result = new Array(len).fill(0);
    const used = new Array(n + 1).fill(false);
    
    function backtrack(pos) {
        if (pos === len) return true;
        if (result[pos] !== 0) return backtrack(pos + 1);
        
        for (let num = n; num >= 1; num--) {
            if (used[num]) continue;
            
            if (num === 1) {
                result[pos] = 1;
                used[1] = true;
                if (backtrack(pos + 1)) return true;
                result[pos] = 0;
                used[1] = false;
            } else {
                const nextPos = pos + num;
                if (nextPos < len && result[nextPos] === 0) {
                    result[pos] = num;
                    result[nextPos] = num;
                    used[num] = true;
                    if (backtrack(pos + 1)) return true;
                    result[pos] = 0;
                    result[nextPos] = 0;
                    used[num] = false;
                }
            }
        }
        return false;
    }
    
    backtrack(0);
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(n! × 2^n)
空间复杂度O(n)

说明：

  • 时间复杂度：在最坏情况下，回溯算法需要尝试所有可能的组合。每个位置最多有 n 种选择，序列长度为 2n-1，因此复杂度较高。但由于题目保证有解且 n≤20，实际运行时间可接受。
  • 空间复杂度：主要包括递归栈空间 O(n) 和存储结果数组的空间 O(n)。

相关题目