难度: Medium
Submission
运行时间: 28 ms
内存: 16.7 MB
class Solution: def isMagic(self, target: List[int]) -> bool: # 这个东西的巧妙之处在于k值的判断 n = len(target) if n == 1: return True nums = [i+1 for i in range(n)] first = nums[1::2] + nums[::2] k = 0 while k < n and first[k] == target[k]: k += 1 if k == 0: return False ans = [] while nums: nums = nums[1::2] + nums[::2] ans.extend(nums[:k]) nums = nums[k:] return ans == target
Explain
该题解通过首先确定可能的k值来检验是否可以通过特定的洗牌方法和取数顺序生成目标数组target。首先生成一个从1到N的数组,然后模拟魔术师的洗牌方法(将偶数位置的卡片放到奇数位置卡片的前面),以此来判定在第一次洗牌后的数组中,最长的和target数组前缀匹配的长度,即为k。接下来,使用这个k值,通过重复洗牌和截取操作来尝试构建一个和target相同的序列。如果通过这种方式完全构建的序列和target相同,返回true;否则,返回false。
时间复杂度: O(n log_k(n))
空间复杂度: O(n)
# 在类Solution内部定义的函数isMagic用于判断能否通过特定的k值生成目标数组target class Solution: def isMagic(self, target: List[int]) -> bool: # 定义函数, 参数为目标数组 n = len(target) # 获取数组长度 if n == 1: # 如果数组长度为1, 返回True return True nums = [i+1 for i in range(n)] # 生成从1到n的数组 first = nums[1::2] + nums[::2] # 首次洗牌,偶数位置的数字放在前面 k = 0 while k < n and first[k] == target[k]: # 确定k的值,即第一次洗牌后与目标数组匹配的最长前缀 k += 1 if k == 0: # 如果k为0,说明没有匹配的前缀,返回False return False ans = [] # 用于存储最终生成的数组 while nums: # 当nums不为空时执行循环 nums = nums[1::2] + nums[::2] # 再次洗牌 ans.extend(nums[:k]) # 取出前k个元素并加到ans中 nums = nums[k:] # 更新nums,去掉已经取出的元素 return ans == target # 比较最终生成的数组与目标数组是否一致,返回比较结果
Explore
在定义函数isMagic时,选择从1到N的顺序来初始化数组是基于题目设定和问题的自然性质。这种顺序代表了一个最自然的、未经处理的序列状态,即连续自然数的最初排列方式。此外,考虑到题目描述中未指明使用非标准初始排列,遵循这一自然顺序有助于简化问题并避免引入不必要的复杂性。实际上,使用其他初始排列可以作为探索或拓展问题的方式,但对于解决标准问题而言,从1到N的顺序是最直接和合适的选择。
在确定k值后,即在第一次洗牌后与target数组匹配的最长前缀长度,该值用于指导后续的洗牌和取数操作。在保证这个k值在后续过程中仍然有效的关键在于,算法的设计必须确保每次洗牌后都能从前k个元素中取出与target对应的元素。算法通过不断地洗牌和按k取数来尝试重建整个target数组。如果在任何一步中,从nums数组中取出的前k个元素无法与target中相应的部分匹配,则整个算法会终止并返回false。因此,k值的有效性是通过算法的控制流和循环中的条件检查来维持的。
当k值非常小,如k=1时,表明每次洗牌后只能从数组中取出一个元素来构建目标数组。在这种情况下,算法需要执行更多次的洗牌和取数操作来完成数组的构建,从而可能导致效率降低。具体来说,如果k=1,则每次洗牌后只取一个元素,这意味着为了构建长度为N的target数组,可能需要进行N次洗牌和取数操作。这显然比较高的k值(如接近N/2)需要更多的计算和时间,因此在k值较小的情况下,算法的效率较低,并可能显著影响性能。