1. 题目背景与核心需求今天我们来拆解LeetCode第3314题构造最小位运算数组 I。这是一道典型的位运算与数组构造结合的题目题目要求我们根据给定的整数数组构造一个新的数组其中每个元素满足特定的位运算条件。题目描述通常如下给定一个整数数组nums构造一个新数组answer使得answer[i]等于nums中除nums[i]之外所有元素的位运算AND结果。位运算AND操作是将两个数的二进制表示逐位进行与运算。注意位运算AND的特性是任何数与0进行AND操作结果都是0而与全1数进行AND操作则保留原数。这个特性在解题中非常关键。这道题看似简单但考察了几个重要知识点位运算的基本原理与应用数组遍历与元素操作算法的时间复杂度优化思路2. 暴力解法分析与实现2.1 最直观的暴力解法对于初学者来说最直接的思路是对于每个元素nums[i]遍历数组中所有其他元素进行位运算AND操作。这种方法虽然直观但时间复杂度为O(n²)在数据量较大时性能会很差。def constructArray(nums): n len(nums) answer [0] * n for i in range(n): temp ~0 # 初始化为全1 for j in range(n): if j ! i: temp nums[j] answer[i] temp return answer这种解法的问题在于对于每个元素都要遍历整个数组进行了大量重复计算没有利用到位运算的特性进行优化2.2 暴力解法的局限性当数组长度为n时暴力解法需要进行n*(n-1)次位运算操作。对于LeetCode的测试用例来说当n达到10^5量级时这种解法肯定会超时。因此我们需要寻找更优化的解决方案。3. 优化思路与数学原理3.1 位运算的数学特性位运算AND有一个重要特性一系列数的AND结果等于这些数在每一位上共同为1的位的组合。也就是说对于最终结果的每一位只有当所有参与运算的数在该位都为1时结果位才为1只要有一个数在该位为0结果位就为0基于这个特性我们可以得出一个重要结论整个数组的AND结果等于所有元素的AND结果。而题目要求的answer[i]其实就是整个数组的AND结果再与nums[i]的逆进行AND操作。3.2 前缀与后缀数组优化我们可以使用前缀和后缀数组的技术来优化计算预先计算从左到右的前缀AND数组预先计算从右到左的后缀AND数组对于每个元素nums[i]answer[i] prefix[i-1] suffix[i1]这种方法将时间复杂度降低到了O(n)只需要三次遍历数组一次计算前缀数组一次计算后缀数组一次计算最终结果def constructArray(nums): n len(nums) prefix [0] * n suffix [0] * n answer [0] * n prefix[0] nums[0] for i in range(1, n): prefix[i] prefix[i-1] nums[i] suffix[-1] nums[-1] for i in range(n-2, -1, -1): suffix[i] suffix[i1] nums[i] answer[0] suffix[1] answer[-1] prefix[-2] for i in range(1, n-1): answer[i] prefix[i-1] suffix[i1] return answer4. 空间复杂度优化4.1 进一步优化思路虽然前缀后缀数组的方法已经很高效但我们还可以进一步优化空间复杂度。观察到在计算answer数组时我们实际上只需要知道prefix[i-1]和suffix[i1]而不需要存储整个前缀和后缀数组。因此我们可以先计算整个数组的AND结果total_and然后对于每个nums[i]answer[i] total_and (~nums[i])不过这种方法有一个前提条件只有当nums[i]在total_and的基础上没有贡献额外的0位时才成立。在实际应用中这种方法可能不总是适用。4.2 最优解法实现经过分析我们发现最可靠的还是前缀后缀数组的方法。下面是经过空间优化的实现def constructArray(nums): n len(nums) answer [0] * n # 先计算后缀数组 answer[-1] nums[-1] for i in range(n-2, -1, -1): answer[i] answer[i1] nums[i] # 再计算前缀并同时计算最终结果 prefix nums[0] final_answer [0] * n final_answer[0] answer[1] for i in range(1, n-1): final_answer[i] prefix answer[i1] prefix nums[i] final_answer[-1] prefix return final_answer这种方法只需要O(1)的额外空间除了输出数组达到了最优的空间复杂度。5. 边界条件与测试用例5.1 常见边界情况在实现这类算法时需要特别注意以下边界条件空数组输入虽然题目保证非空单元素数组全0数组全1数组大数数组接近整数最大值混合正负数数组5.2 测试用例设计好的测试用例应该包含test_cases [ ([1,2,3,4], [0,1,0,0]), # 常规情况 ([0,0,0,0], [0,0,0,0]), # 全0 ([1,1,1,1], [1,1,1,1]), # 全1 ([1,3,5,7], [1,1,1,1]), # 奇数特例 ([2,4,8,16], [0,0,0,0]), # 不同位 ([1], [0]), # 单元素 ([255,255,255], [255,255,255]) # 全255 ]6. 复杂度分析与比较6.1 时间复杂度对比暴力解法O(n²)对于每个元素遍历其他所有元素不适合大规模数据前缀后缀数组O(n)三次线性遍历适合大规模数据空间优化版O(n)两次线性遍历同样适合大规模数据6.2 空间复杂度对比暴力解法O(1)不包括输出数组只需要常数空间但时间复杂度太高前缀后缀数组O(n)需要存储前缀和后缀数组空间开销较大空间优化版O(1)不包括输出数组最优的空间复杂度只需要常数额外空间7. 实际应用与扩展7.1 位运算的实际应用场景位运算在计算机科学中有广泛应用权限控制系统如Linux文件权限数据压缩与编码哈希算法图形处理如像素操作网络协议如IP地址处理7.2 题目扩展思考这道题可以有多种变体使用OR运算代替AND运算使用XOR运算组合多种位运算三维数组的位运算处理流式数据的位运算处理例如如果题目改为OR运算我们可以使用类似的优化思路但需要注意OR运算的特性任何数与1进行OR操作结果都是1。8. 刷题建议与技巧8.1 位运算常见技巧判断奇偶x 1取最低位的1x -x将最低位的1变为0x (x-1)判断是否为2的幂x (x-1) 0交换两个数a ^ b; b ^ a; a ^ b;8.2 LeetCode刷题策略先理解题目要求明确输入输出思考暴力解法确保理解题意分析时间/空间复杂度寻找优化点考虑数据结构和算法技巧的应用编写代码并测试边界条件反思是否有更优解对于位运算题目特别要注意二进制表示的特性位运算的数学性质常见位运算技巧的应用场景9. 从简单题到难题的过渡这道题目标为I意味着可能有更复杂的II版本。在实际刷题中我们应该先掌握基础解法理解优化思路思考如何应对更大规模数据考虑问题的各种变体将解法抽象成通用模式对于后续的II版本可能会涉及更大的数据规模更复杂的位运算组合动态数据更新多维数组处理分布式计算环境下的处理10. 个人实战经验分享在实际解决这类问题时我总结了一些经验位运算题目常常有灵光一现的特性需要多练习培养直觉画二进制表示图有助于理解问题小规模手动计算可以帮助验证思路注意整数溢出问题Python中不用担心但其他语言需要考虑位运算优先级较低多用括号明确运算顺序一个常见的坑是忽略位运算的优先级。例如# 错误写法 if x 1 0: # 实际是 x (1 0) pass # 正确写法 if (x 1) 0: pass另一个实用技巧是使用掩码来操作特定位# 设置第k位为1 def set_bit(x, k): return x | (1 k) # 清除第k位 def clear_bit(x, k): return x ~(1 k) # 切换第k位 def toggle_bit(x, k): return x ^ (1 k)最后对于LeetCode刷题建议建立一个位运算工具函数库把常用操作封装起来可以大大提高解题效率。 LeetCode 3314：位运算数组构造与优化解法详解
1. 题目背景与核心需求今天我们来拆解LeetCode第3314题构造最小位运算数组 I。这是一道典型的位运算与数组构造结合的题目题目要求我们根据给定的整数数组构造一个新的数组其中每个元素满足特定的位运算条件。题目描述通常如下给定一个整数数组nums构造一个新数组answer使得answer[i]等于nums中除nums[i]之外所有元素的位运算AND结果。位运算AND操作是将两个数的二进制表示逐位进行与运算。注意位运算AND的特性是任何数与0进行AND操作结果都是0而与全1数进行AND操作则保留原数。这个特性在解题中非常关键。这道题看似简单但考察了几个重要知识点位运算的基本原理与应用数组遍历与元素操作算法的时间复杂度优化思路2. 暴力解法分析与实现2.1 最直观的暴力解法对于初学者来说最直接的思路是对于每个元素nums[i]遍历数组中所有其他元素进行位运算AND操作。这种方法虽然直观但时间复杂度为O(n²)在数据量较大时性能会很差。def constructArray(nums): n len(nums) answer [0] * n for i in range(n): temp ~0 # 初始化为全1 for j in range(n): if j ! i: temp nums[j] answer[i] temp return answer这种解法的问题在于对于每个元素都要遍历整个数组进行了大量重复计算没有利用到位运算的特性进行优化2.2 暴力解法的局限性当数组长度为n时暴力解法需要进行n*(n-1)次位运算操作。对于LeetCode的测试用例来说当n达到10^5量级时这种解法肯定会超时。因此我们需要寻找更优化的解决方案。3. 优化思路与数学原理3.1 位运算的数学特性位运算AND有一个重要特性一系列数的AND结果等于这些数在每一位上共同为1的位的组合。也就是说对于最终结果的每一位只有当所有参与运算的数在该位都为1时结果位才为1只要有一个数在该位为0结果位就为0基于这个特性我们可以得出一个重要结论整个数组的AND结果等于所有元素的AND结果。而题目要求的answer[i]其实就是整个数组的AND结果再与nums[i]的逆进行AND操作。3.2 前缀与后缀数组优化我们可以使用前缀和后缀数组的技术来优化计算预先计算从左到右的前缀AND数组预先计算从右到左的后缀AND数组对于每个元素nums[i]answer[i] prefix[i-1] suffix[i1]这种方法将时间复杂度降低到了O(n)只需要三次遍历数组一次计算前缀数组一次计算后缀数组一次计算最终结果def constructArray(nums): n len(nums) prefix [0] * n suffix [0] * n answer [0] * n prefix[0] nums[0] for i in range(1, n): prefix[i] prefix[i-1] nums[i] suffix[-1] nums[-1] for i in range(n-2, -1, -1): suffix[i] suffix[i1] nums[i] answer[0] suffix[1] answer[-1] prefix[-2] for i in range(1, n-1): answer[i] prefix[i-1] suffix[i1] return answer4. 空间复杂度优化4.1 进一步优化思路虽然前缀后缀数组的方法已经很高效但我们还可以进一步优化空间复杂度。观察到在计算answer数组时我们实际上只需要知道prefix[i-1]和suffix[i1]而不需要存储整个前缀和后缀数组。因此我们可以先计算整个数组的AND结果total_and然后对于每个nums[i]answer[i] total_and (~nums[i])不过这种方法有一个前提条件只有当nums[i]在total_and的基础上没有贡献额外的0位时才成立。在实际应用中这种方法可能不总是适用。4.2 最优解法实现经过分析我们发现最可靠的还是前缀后缀数组的方法。下面是经过空间优化的实现def constructArray(nums): n len(nums) answer [0] * n # 先计算后缀数组 answer[-1] nums[-1] for i in range(n-2, -1, -1): answer[i] answer[i1] nums[i] # 再计算前缀并同时计算最终结果 prefix nums[0] final_answer [0] * n final_answer[0] answer[1] for i in range(1, n-1): final_answer[i] prefix answer[i1] prefix nums[i] final_answer[-1] prefix return final_answer这种方法只需要O(1)的额外空间除了输出数组达到了最优的空间复杂度。5. 边界条件与测试用例5.1 常见边界情况在实现这类算法时需要特别注意以下边界条件空数组输入虽然题目保证非空单元素数组全0数组全1数组大数数组接近整数最大值混合正负数数组5.2 测试用例设计好的测试用例应该包含test_cases [ ([1,2,3,4], [0,1,0,0]), # 常规情况 ([0,0,0,0], [0,0,0,0]), # 全0 ([1,1,1,1], [1,1,1,1]), # 全1 ([1,3,5,7], [1,1,1,1]), # 奇数特例 ([2,4,8,16], [0,0,0,0]), # 不同位 ([1], [0]), # 单元素 ([255,255,255], [255,255,255]) # 全255 ]6. 复杂度分析与比较6.1 时间复杂度对比暴力解法O(n²)对于每个元素遍历其他所有元素不适合大规模数据前缀后缀数组O(n)三次线性遍历适合大规模数据空间优化版O(n)两次线性遍历同样适合大规模数据6.2 空间复杂度对比暴力解法O(1)不包括输出数组只需要常数空间但时间复杂度太高前缀后缀数组O(n)需要存储前缀和后缀数组空间开销较大空间优化版O(1)不包括输出数组最优的空间复杂度只需要常数额外空间7. 实际应用与扩展7.1 位运算的实际应用场景位运算在计算机科学中有广泛应用权限控制系统如Linux文件权限数据压缩与编码哈希算法图形处理如像素操作网络协议如IP地址处理7.2 题目扩展思考这道题可以有多种变体使用OR运算代替AND运算使用XOR运算组合多种位运算三维数组的位运算处理流式数据的位运算处理例如如果题目改为OR运算我们可以使用类似的优化思路但需要注意OR运算的特性任何数与1进行OR操作结果都是1。8. 刷题建议与技巧8.1 位运算常见技巧判断奇偶x 1取最低位的1x -x将最低位的1变为0x (x-1)判断是否为2的幂x (x-1) 0交换两个数a ^ b; b ^ a; a ^ b;8.2 LeetCode刷题策略先理解题目要求明确输入输出思考暴力解法确保理解题意分析时间/空间复杂度寻找优化点考虑数据结构和算法技巧的应用编写代码并测试边界条件反思是否有更优解对于位运算题目特别要注意二进制表示的特性位运算的数学性质常见位运算技巧的应用场景9. 从简单题到难题的过渡这道题目标为I意味着可能有更复杂的II版本。在实际刷题中我们应该先掌握基础解法理解优化思路思考如何应对更大规模数据考虑问题的各种变体将解法抽象成通用模式对于后续的II版本可能会涉及更大的数据规模更复杂的位运算组合动态数据更新多维数组处理分布式计算环境下的处理10. 个人实战经验分享在实际解决这类问题时我总结了一些经验位运算题目常常有灵光一现的特性需要多练习培养直觉画二进制表示图有助于理解问题小规模手动计算可以帮助验证思路注意整数溢出问题Python中不用担心但其他语言需要考虑位运算优先级较低多用括号明确运算顺序一个常见的坑是忽略位运算的优先级。例如# 错误写法 if x 1 0: # 实际是 x (1 0) pass # 正确写法 if (x 1) 0: pass另一个实用技巧是使用掩码来操作特定位# 设置第k位为1 def set_bit(x, k): return x | (1 k) # 清除第k位 def clear_bit(x, k): return x ~(1 k) # 切换第k位 def toggle_bit(x, k): return x ^ (1 k)最后对于LeetCode刷题建议建立一个位运算工具函数库把常用操作封装起来可以大大提高解题效率。