Hard

题目描述

给你一个整数数组 nums 和两个整数 k 和 m。

你最多可以执行 k 次操作。在一次操作中，你可以选择任意索引 i 并将 nums[i] 增加 1。

返回在最优执行最多 k 次操作后，任意大小为 m 的子集的最大可能按位与值。

示例 1：

输入：nums = [3,1,2], k = 8, m = 2
输出：6
解释：
我们需要一个大小为 m = 2 的子集。选择索引 [0, 2]。
将 nums[0] = 3 增加到 6，使用 3 次操作，将 nums[2] = 2 增加到 6，使用 4 次操作。
使用的操作总数是 7，不超过 k = 8。
选择的两个值变成 [6, 6]，它们的按位与是 6，这是最大可能值。

示例 2：

输入：nums = [1,2,8,4], k = 7, m = 3
输出：4
解释：
我们需要一个大小为 m = 3 的子集。选择索引 [0, 1, 3]。
将 nums[0] = 1 增加到 4，使用 3 次操作，将 nums[1] = 2 增加到 4，使用 2 次操作，保持 nums[3] = 4。
使用的操作总数是 5，不超过 k = 7。
选择的三个值变成 [4, 4, 4]，它们的按位与是 4，这是最大可能值。

示例 3：

输入：nums = [1,1], k = 3, m = 2
输出：2
解释：
我们需要一个大小为 m = 2 的子集。选择索引 [0, 1]。
将两个值都从 1 增加到 2，每个使用 1 次操作。
使用的操作总数是 2，不超过 k = 3。
选择的两个值变成 [2, 2]，它们的按位与是 2，这是最大可能值。

约束：

  • 1 <= n == nums.length <= 5 * 10^4
  • 1 <= nums[i] <= 10^9
  • 1 <= k <= 10^9
  • 1 <= m <= n

解题思路

这是一道关于位操作和贪心算法的困难题。核心思路是从最高位开始逐位尝试，贪心地构造最大的按位与结果。

算法思路：

  1. 位操作贪心策略：按位与的特点是所有参与运算的数在某一位都为1时，结果的对应位才为1。因此我们从最高位开始，逐位尝试在结果中设置该位为1。

  2. 可行性检验：对于当前候选结果 candidate，检查是否能用不超过 k 次操作使得至少 m 个数满足要求。具体地，对于每个数 num，计算使其满足 (num | candidate) == candidate 所需的最少操作次数。

  3. 操作次数计算：要使 num 满足条件，需要将 num 的某些位设置为1。所需操作次数为 max(0, candidate - num)，但需要考虑位操作的特殊性：如果 num 在 candidate 为1的位上已经是1，则不需要额外操作。

  4. 选择最优子集：计算所有数的操作代价后，选择代价最小的 m 个数，检查总代价是否不超过 k。

  5. 逐位构造：从高位到低位，对每一位尝试设置为1，如果可行则保留，否则该位设置为0。

这种贪心策略是正确的，因为高位对最终结果的贡献更大，优先确保高位为1能获得更大的按位与值。

代码实现

class Solution {
public:
    int maximumAND(vector<int>& nums, int k, int m) {
        int n = nums.size();
        int result = 0;
        
        // 从最高位开始尝试
        for (int bit = 30; bit >= 0; bit--) {
            int candidate = result | (1 << bit);
            vector<long long> costs;
            
            // 计算每个数达到candidate所需的最小代价
            for (int num : nums) {
                if ((num & candidate) == candidate) {
                    // num已经包含candidate的所有位，无需操作
                    costs.push_back(0);
                } else {
                    // 需要将num提升到至少candidate
                    costs.push_back((long long)candidate - num);
                }
            }
            
            // 排序取最小的m个代价
            sort(costs.begin(), costs.end());
            long long totalCost = 0;
            for (int i = 0; i < m; i++) {
                totalCost += costs[i];
            }
            
            // 如果总代价不超过k，则可以设置这一位
            if (totalCost <= k) {
                result = candidate;
            }
        }
        
        return result;
    }
};

class Solution:
    def maximumAND(self, nums: List[int], k: int, m: int) -> int:
        result = 0
        
        # 从最高位开始尝试
        for bit in range(30, -1, -1):
            candidate = result | (1 << bit)
            costs = []
            
            # 计算每个数达到candidate所需的最小代价
            for num in nums:
                if (num & candidate) == candidate:
                    # num已经包含candidate的所有位，无需操作
                    costs.append(0)
                else:
                    # 需要将num提升到至少candidate
                    costs.append(candidate - num)
            
            # 排序取最小的m个代价
            costs.sort()
            total_cost = sum(costs[:m])
            
            # 如果总代价不超过k，则可以设置这一位
            if total_cost <= k:
                result = candidate
        
        return result

public class Solution {
    public int MaximumAND(int[] nums, int k, int m) {
        int result = 0;
        
        // 从最高位开始尝试
        for (int bit = 30; bit >= 0; bit--) {
            int candidate = result | (1 << bit);
            var costs = new List<long>();
            
            // 计算每个数达到candidate所需的最小代价
            foreach (int num in nums) {
                if ((num & candidate) == candidate) {
                    // num已经包含candidate的所有位，无需操作
                    costs.Add(0);
                } else {
                    // 需要将num提升到至少candidate
                    costs.Add((long)candidate - num);
                }
            }
            
            // 排序取最小的m个代价
            costs.Sort();
            long totalCost = 0;
            for (int i = 0; i < m; i++) {
                totalCost += costs[i];
            }
            
            // 如果总代价不超过k，则可以设置这一位
            if (totalCost <= k) {
                result = candidate;
            }
        }
        
        return result;
    }
}

/**
 * @param {number[]} nums
 * @param {number} k
 * @param {number} m
 * @return {number}
 */
var maximumAND = function(nums, k, m) {
    const canAchieve = (target) => {
        const costs = nums.map(num => Math.max(0, target - num));
        costs.sort((a, b) => a - b);
        const totalCost = costs.slice(0, m).reduce((sum, cost) => sum + cost, 0);
        return totalCost <= k;
    };
    
    let left = 0, right = Math.max(...nums) + k;
    let result = 0;
    
    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        if (canAchieve(mid)) {
            result = mid;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型时间复杂度空间复杂度
最优解法O(31 × n log n)O(n)

说明：

  • 时间复杂度：需要检查31个位（从30到0），每次检查需要O(n log n)的排序时间
  • 空间复杂度：需要O(n)的额外空间存储每个数的操作代价