题目描述
秋日市集上,魔术师邀请小扣与他互动。魔术师的道具为分别写有数字 1~N
的 N
张卡牌,然后请小扣思考一个 N
张卡牌的排列 target
。
魔术师的目标是找到一个数字 k
(k >= 1
),使得初始排列顺序为 1~N
的卡牌经过特殊的洗牌方式最终变成小扣所想的排列 target,特殊的洗牌方式为:
- 第一步,魔术师将当前位于 偶数位置 的卡牌(下标自
1
开始),保持 当前排列顺序 放在位于 奇数位置 的卡牌之前。例如:将当前排列[1,2,3,4,5]
位于偶数位置的[2,4]
置于奇数位置的[1,3,5]
前,排列变为[2,4,1,3,5]
; - 第二步,若当前卡牌数量小于等于
k
,则魔术师按排列顺序取走全部卡牌;若当前卡牌数量大于k
,则取走前k
张卡牌,剩余卡牌继续重复这两个步骤,直至所有卡牌全部被取走;
卡牌按照魔术师取走顺序构成的新排列为「魔术取数排列」,请返回是否存在这个数字 k
使得「魔术取数排列」恰好就是 target
,从而让小扣感到大吃一惊。
样例
输入:target = [2,4,3,1,5]
输出:true
解释:
排列 target 长度为 5,初始排列为:1,2,3,4,5。
我们选择 k = 2:
第一次:将当前排列 [1,2,3,4,5] 位于偶数位置的 [2,4] 置于奇数位置的 [1,3,5] 前,
排列变为 [2,4,1,3,5]。取走前 2 张卡牌 2,4,剩余 [1,3,5];
第二次:将当前排列 [1,3,5] 位于偶数位置的 [3] 置于奇数位置的 [1,5] 前,排列变为 [3,1,5]。
取走前 2 张 3,1,剩余 [5];
第三次:当前排列为 [5],全部取出。
最后,数字按照取出顺序构成的「魔术取数排列」2,4,3,1,5 恰好为 target。
输入:target = [5,4,3,2,1]
输出:false
解释:无法找到一个数字 k 可以使「魔术取数排列」恰好为 target。
限制
1 <= target.length = N <= 5000
- 题目保证
target
是1~N
的一个排列。
算法
(模拟) $O(n^2)$
- 按照题目描述模拟。
- 每一轮先做第一步,做完后和
target
数组匹配,得到一个匹配度t
。 - 比对除了最后一轮外的,其余的匹配度是否都相同且大于 0。
时间复杂度
- 每一轮至少会减少一个数字,需要 $O(n)$ 的时间。
- 故总时间复杂度为 $O(n^2)$。
空间复杂度
- 需要 $O(n)$ 的额外空间模拟整个过程。
C++ 代码
class Solution {
public:
bool isMagic(vector<int>& target) {
const int n = target.size();
vector<int> x;
for (int i = 1; i <= n; i++)
x.push_back(i);
int k = -1;
int pos = 0; // pos 记录当前 target 匹配到的位置
while (pos < n) {
vector<int> y;
// 移动卡牌
for (int i = 1; i < x.size(); i += 2)
y.push_back(x[i]);
for (int i = 0; i < x.size(); i += 2)
y.push_back(x[i]);
// 匹配 target
int t = 0;
for (int i = 0; i < y.size(); i++, t++, pos++)
if (y[i] != target[pos])
break;
// 匹配失败,直接返回失败
if (t == 0)
return false;
if (k == -1) { // 第一次匹配
k = t;
} else { // 不是第一次匹配
if (pos == n) // 如果是最后一次匹配,返回成功
return true;
if (k != t) // 如果和之前的匹配度不一致,返回失败
return false;
}
x.clear(); // 取出匹配剩余的数组
for (int i = t; i < y.size(); i++)
x.push_back(y[i]);
}
return true;
}
};