LeetCode 数组中两个元素的最大与题解
LeetCode 数组中两个元素的最大与题解
题目描述
给定一个非空整数数组，找出数组中最大的按位与结果（即所有元素进行按位与运算的结果）。
示例：
输入：nums = [16,8,4]
输出：0
输入：nums = [4,6,7]
输出：4
解题思路
方法：位运算
思路：
- 使用位运算来解决这个问题。
- 找出所有数字的公共前缀。
- 从左到右遍历每一位，如果这一位上所有数字都是 1，则该位为 1。
- 否则，该位为 0。
- 最终结果就是公共前缀对应的数字。
复杂度分析：
- 时间复杂度：O(n * k)，其中 n 是数组长度，k 是整数的位数。
- 空间复杂度：O(1)。
代码实现
方法：位运算
# 数组中两个元素的最大与（位运算） def largest_xor(nums): result = 0 for i in range(31, -1, -1): result = (1 << i) + 1 if i == 31 else 0 break mask = 0 for i in range(31, -1, -1): mask |= (1 << i) seen = set() for num in nums: seen.add(num & mask) if len(seen) > 1: mask ^= (1 << i) return mask # 测试 def test_largest_xor(): nums = [16, 8, 4] print(largest_xor(nums)) # 输出：0 nums = [4, 6, 7] print(largest_xor(nums)) # 输出：4 if __name__ == "__main__": test_largest_xor()测试用例
测试用例 1：基本情况1
输入：nums = [16,8,4]
输出：0
测试用例 2：基本情况2
输入：nums = [4,6,7]
输出：4
总结
数组中两个元素的最大与是一个经典的位运算问题，它可以通过位运算来高效地解决。
位运算的核心思想是：找出所有数字的公共前缀。
掌握位运算的使用方法，对于解决类似的问题非常重要。