Medium

题目描述

给你一个长度为 n 的下标从 0 开始的整数数组 nums 和一个整数 k。在一次操作中，你可以选择一个元素并将它乘以 2。

返回在对 nums 应用至多 k 次操作后，可以得到的 nums[0] | nums[1] | … | nums[n - 1] 的最大可能值。

注意 a | b 表示两个整数 a 和 b 的按位或运算。

示例 1：

输入：nums = [12,9], k = 1
输出：30
解释：如果我们对下标 1 应用操作，我们的新数组 nums 将等于 [12,18]。因此，我们返回 12 和 18 的按位或，即 30。

示例 2：

输入：nums = [8,1,2], k = 2
输出：35
解释：如果我们对下标 0 应用操作两次，我们得到新数组 [32,1,2]。因此，我们返回 32|1|2 = 35。

约束条件：

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^9
  • 1 <= k <= 15

解题思路

这道题要求通过最多 k 次乘以 2 的操作，使得数组所有元素按位或的结果最大。

核心洞察： 由于按位或运算的特性，为了最大化结果，应该将所有 k 次操作都应用在同一个数字上。这是因为：

  1. 乘以 2 相当于左移一位，会使数字的高位比特位被设置
  2. 按位或运算中，只要有一个数字的某个比特位为 1，结果的对应位就为 1
  3. 因此集中操作一个数字能够最有效地设置高位比特位

算法思路：

  1. 预计算前缀或数组：prefix[i] 表示 nums[0] | nums[1] | … | nums[i-1]
  2. 预计算后缀或数组：suffix[i] 表示 nums[i+1] | nums[i+2] | … | nums[n-1]
  3. 对每个位置 i，计算如果将所有 k 次操作都应用在 nums[i] 上的结果
  4. 该位置的最终结果 = prefix[i] | (nums[i] « k) | suffix[i]
  5. 返回所有位置中的最大值

这种方法的时间复杂度是 O(n)，空间复杂度也是 O(n)，非常高效。

代码实现

class Solution {
public:
    long long maximumOr(vector<int>& nums, int k) {
        int n = nums.size();
        vector<long long> prefix(n + 1, 0), suffix(n + 1, 0);
        
        // 计算前缀或
        for (int i = 0; i < n; i++) {
            prefix[i + 1] = prefix[i] | nums[i];
        }
        
        // 计算后缀或
        for (int i = n - 1; i >= 0; i--) {
            suffix[i] = suffix[i + 1] | nums[i];
        }
        
        long long maxOr = 0;
        for (int i = 0; i < n; i++) {
            // 将所有k次操作应用在nums[i]上
            long long currentOr = prefix[i] | ((long long)nums[i] << k) | suffix[i + 1];
            maxOr = max(maxOr, currentOr);
        }
        
        return maxOr;
    }
};

class Solution:
    def maximumOr(self, nums: List[int], k: int) -> int:
        n = len(nums)
        prefix = [0] * (n + 1)
        suffix = [0] * (n + 1)
        
        # 计算前缀或
        for i in range(n):
            prefix[i + 1] = prefix[i] | nums[i]
        
        # 计算后缀或
        for i in range(n - 1, -1, -1):
            suffix[i] = suffix[i + 1] | nums[i]
        
        max_or = 0
        for i in range(n):
            # 将所有k次操作应用在nums[i]上
            current_or = prefix[i] | (nums[i] << k) | suffix[i + 1]
            max_or = max(max_or, current_or)
        
        return max_or

public class Solution {
    public long MaximumOr(int[] nums, int k) {
        int n = nums.Length;
        long[] prefix = new long[n + 1];
        long[] suffix = new long[n + 1];
        
        // 计算前缀或
        for (int i = 0; i < n; i++) {
            prefix[i + 1] = prefix[i] | nums[i];
        }
        
        // 计算后缀或
        for (int i = n - 1; i >= 0; i--) {
            suffix[i] = suffix[i + 1] | nums[i];
        }
        
        long maxOr = 0;
        for (int i = 0; i < n; i++) {
            // 将所有k次操作应用在nums[i]上
            long currentOr = prefix[i] | ((long)nums[i] << k) | suffix[i + 1];
            maxOr = Math.Max(maxOr, currentOr);
        }
        
        return maxOr;
    }
}

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var maximumOr = function(nums, k) {
    const n = nums.length;
    const prefix = new Array(n + 1).fill(0);
    const suffix = new Array(n + 1).fill(0);
    
    // 计算前缀或
    for (let i = 0; i < n; i++) {
        prefix[i + 1] = prefix[i] | nums[i];
    }
    
    // 计算后缀或
    for (let i = n - 1; i >= 0; i--) {
        suffix[i] = suffix[i + 1] | nums[i];
    }
    
    let maxOr = 0;
    for (let i = 0; i < n; i++) {
        // 将所有k次操作应用在nums[i]上
        const currentOr = prefix[i] | (nums[i] << k) | suffix[i + 1];
        maxOr = Math.max(maxOr, currentOr);
    }
    
    return maxOr;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度
时间复杂度O(n)
空间复杂度O(n)

其中 n 是数组 nums 的长度。我们需要遍历数组三次：一次计算前缀或，一次计算后缀或，一次计算最终答案，每次都是 O(n)。空间复杂度为 O(n)，用于存储前缀和后缀或数组。