题目描述
给你两个整数 n
和 start
。你的任务是返回 任意 (0, 1, 2, ..., 2^n-1)
的排列 p
,并且满足:
p[0] = start
p[i]
和p[i+1]
的二进制表示形式只有一位不同。p[0]
和p[2^n-1]
的二进制表示形式也只有一位不同。
样例
输入:n = 2, start = 3
输出:[3,2,0,1]
解释:这个排列的二进制表示是 (11,10,00,01)
所有的相邻元素都有一位是不同的,另一个有效的排列是 [3,1,0,2]
输出:n = 3, start = 2
输出:[2,6,7,5,4,0,1,3]
解释:这个排列的二进制表示是 (010,110,111,101,100,000,001,011)
限制
1 <= n <= 16
0 <= start < 2^n
算法
(构造) $O(n2^n)$
- 我们仅考虑
start
从 0 开始的情况,其余情况可以让start
异或整个以 0 开始的排列得到新的排列。 - 假设
start = 0
,则我们按照如下的方式构造,每一次从最低位开始试,判断当前位翻转之后的数字是否出现过,如果没有出现过,则他就是下一个数字。 - 以四位数为例,顺序如下
(0000, 0001, 0011, 0010, 0110, 0111, 0101, 0100, 1100, 1101, 1111, 1110, 1010, 1011, 1001, 1000)
。 - 注意这里必须按照某个试的顺序来找下一个数字,即不能随机找一个可以翻转的位,如
(000, 001, 011, 111, 110, 100, ?)
,则最后的010
无法放入。
时间复杂度
- 找下一个数字需要 $O(n)$ 的复杂度,故总时间复杂度为 $O(n2^n)$。
空间复杂度
- 需要 $O(2^n)$ 的空间存储答案。
C++ 代码
class Solution {
public:
vector<int> circularPermutation(int n, int start) {
vector<int> ans(1 << n);
vector<bool> vis(1 << n, false);
ans[0] = start;
vis[start] = true;
for (int i = 1; i < (1 << n); i++) {
for (int j = 0; j < n; j++) {
int t = start ^ (1 << j);
if (!vis[t]) {
start = t;
break;
}
}
vis[start] = true;
ans[i] = start;
}
return ans;
}
};