题目描述
给定一个整数 n
,请你找到满足下面条件的一个序列:
- 整数
1
在序列中只出现一次。 2
到n
之间每个整数都恰好出现两次。- 对于每个
2
到n
之间的整数i
,两个i
之间出现的距离恰好为i
。
序列里面两个数 a[i]
和 a[j]
之间的 距离,我们定义为它们下标绝对值之差 |j - i|
。
请你返回满足上述条件中 字典序最大 的序列。题目保证在给定限制条件下,一定存在解。
一个序列 a
被认为比序列 b
(两者长度相同)字典序更大的条件是:a
和 b
中第一个不一样的数字处,a
序列的数字比 b
序列的数字大。比方说,[0,1,9,0]
比 [0,1,5,6]
字典序更大,因为第一个不同的位置是第三个数字,且 9
比 5
大。
样例
输入:n = 3
输出:[3,1,2,3,2]
解释:[2,3,2,1,3] 也是一个可行的序列,但是 [3,1,2,3,2] 是字典序最大的序列。
输入:n = 5
输出:[5,3,1,4,3,5,2,4,2]
限制
1 <= n <= 20
算法
(递归回溯) $O(n!)$
- 暴力递归回溯,对当前没有放置数字过的位置,枚举还尚未填充的数字,并一次性填充两个相同的数。
时间复杂度
- 理论时间复杂度为 $O(n!)$,但实际上由于限制很多,暴搜可以很快出答案。
空间复杂度
- 需要 $O(n)$ 的额外空间存储求解的过程和递归的系统栈。
C++ 代码
class Solution {
private:
vector<bool> used;
vector<int> cur;
bool solve(int x, int n) {
if (x == 2 * n - 1) {
return true;
}
if (cur[x] != -1) {
return solve(x + 1, n);
}
for (int i = n; i >= 2; i--) {
if (used[i]) continue;
if (x + i < 2 * n - 1 && cur[x + i] == -1) {
cur[x] = cur[x + i] = i;
used[i] = true;
if (solve(x + 1, n)) {
return true;
}
used[i] = false;
cur[x] = cur[x + i] = -1;
}
}
if (!used[1]) {
cur[x] = 1;
used[1] = true;
if (solve(x + 1, n))
return true;
cur[x] = -1;
used[1] = false;
}
return false;
}
public:
vector<int> constructDistancedSequence(int n) {
used.resize(n + 1, false);
cur.resize(2 * n - 1, -1);
solve(0, n);
return cur;
}
};