Easy

题目描述

给你一个正整数数组 nums。

你需要检查是否可以选择数组中的两个或更多元素，使得这些元素的按位或运算结果在其二进制表示中至少有一个尾随零。

例如，5 的二进制表示是 “101”，没有尾随零，而 4 的二进制表示是 “100”，有两个尾随零。

如果可以选择两个或更多元素，使得它们的按位或运算有尾随零，返回 true，否则返回 false。

示例 1：

输入：nums = [1,2,3,4,5]
输出：true
解释：如果我们选择元素 2 和 4，它们的按位或是 6，二进制表示为 "110"，有一个尾随零。

示例 2：

输入：nums = [2,4,8,16]
输出：true
解释：如果我们选择元素 2 和 4，它们的按位或是 6，二进制表示为 "110"，有一个尾随零。
其他可能的选择方式有：(2, 8), (2, 16), (4, 8), (4, 16), (8, 16), (2, 4, 8), (2, 4, 16), (2, 8, 16), (4, 8, 16), 和 (2, 4, 8, 16)。

示例 3：

输入：nums = [1,3,5,7,9]
输出：false
解释：没有可能的方式选择两个或更多元素使得它们的按位或运算有尾随零。

约束条件：

  • 2 <= nums.length <= 100
  • 1 <= nums[i] <= 100

解题思路

要使按位或运算的结果有尾随零，最后一位必须是 0。由于按位或运算的特性（只要有一个操作数的某一位是 1，结果的该位就是 1），要使结果的最后一位是 0，所有参与运算的数的最后一位都必须是 0。

换句话说，所有参与运算的数都必须是偶数。

解法分析：

  1. 暴力解法：遍历所有可能的数对，对每一对进行按位或运算，检查结果是否有尾随零。时间复杂度 O(n²)。

  2. 优化解法（推荐）：关键观察是，要使按位或运算结果的最低位为 0，所有参与运算的数的最低位都必须为 0，即都必须是偶数。因此问题简化为：数组中是否至少有两个偶数。

这个优化基于一个重要性质：如果存在解决方案，必然存在只使用两个元素的解决方案。因为按位或运算不会清除已设置的位，添加更多元素只会增加更多的 1 位。

算法步骤：

  1. 遍历数组，统计偶数的个数
  2. 如果偶数个数 ≥ 2，返回 true
  3. 否则返回 false

时间复杂度从 O(n²) 优化到 O(n)，空间复杂度 O(1)。

代码实现

class Solution {
public:
    bool hasTrailingZeros(vector<int>& nums) {
        int evenCount = 0;
        for (int num : nums) {
            if (num % 2 == 0) {
                evenCount++;
                if (evenCount >= 2) {
                    return true;
                }
            }
        }
        return false;
    }
};

class Solution:
    def hasTrailingZeros(self, nums: List[int]) -> bool:
        even_count = 0
        for num in nums:
            if num % 2 == 0:
                even_count += 1
                if even_count >= 2:
                    return True
        return False

public class Solution {
    public bool HasTrailingZeros(int[] nums) {
        int evenCount = 0;
        foreach (int num in nums) {
            if (num % 2 == 0) {
                evenCount++;
                if (evenCount >= 2) {
                    return true;
                }
            }
        }
        return false;
    }
}

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var hasTrailingZeros = function(nums) {
    let evenCount = 0;
    for (let num of nums) {
        if (num % 2 === 0) {
            evenCount++;
            if (evenCount >= 2) return true;
        }
    }
    return false;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型数值说明
时间复杂度O(n)最坏情况下需要遍历整个数组，最好情况下提前返回
空间复杂度O(1)只使用常数级别的额外空间

相关题目