Hard

题目描述

给你一个下标从 0 开始的整数数组 nums 和一个正整数 k。

你可以对数组执行下述操作 任意次：

  • 选择两个不同的下标 i 和 j，同时 将 nums[i] 更新为 (nums[i] AND nums[j]) 和将 nums[j] 更新为 (nums[i] OR nums[j])，其中 OR 表示按位或运算，AND 表示按位与运算。

你需要从最终的数组中选择 k 个元素并计算它们的平方和。

返回你能够得到的 最大 平方和。

由于答案可能非常大，返回它对 109 + 7 取余的结果。

示例 1：

输入：nums = [2,6,5,8], k = 2
输出：261
解释：我们可以对数组执行以下操作：
- 选择 i = 0 和 j = 3，然后将 nums[0] 更新为 (2 AND 8) = 0，将 nums[3] 更新为 (2 OR 8) = 10。结果数组为 nums = [0,6,5,10]。
- 选择 i = 2 和 j = 3，然后将 nums[2] 更新为 (5 AND 10) = 0，将 nums[3] 更新为 (5 OR 10) = 15。结果数组为 nums = [0,6,0,15]。
我们可以从最终数组中选择元素 15 和 6。平方和为 152 + 62 = 261。
可以证明这是我们能够得到的最大值。

示例 2：

输入：nums = [4,5,4,7], k = 3
输出：90
解释：我们不需要应用任何操作。
我们可以选择元素 7、5 和 4，平方和为：72 + 52 + 42 = 90。
可以证明这是我们能够得到的最大值。

提示：

  • 1 <= k <= nums.length <= 105
  • 1 <= nums[i] <= 109

解题思路

解题思路

这道题的关键在于理解位操作的性质和最优策略。

核心观察：

  1. 操作 (nums[i] AND nums[j]) 和 (nums[i] OR nums[j]) 实际上是在两个数之间转移比特位
  2. 对于任意两个数的某个比特位，AND操作会将该位设为0（如果至少有一个数在该位为0），OR操作会将该位设为1（如果至少有一个数在该位为1）
  3. 总的比特数量是守恒的 - 我们只能重新分配现有的比特

最优策略： 为了最大化k个数的平方和，我们应该让这k个数尽可能大。由于平方函数是凸函数，集中比特位到少数几个数上会产生更大的平方和。

算法步骤：

  1. 统计所有数字在每个比特位上1的总数
  2. 贪心地构造k个数：对于每个比特位，优先分配给能产生最大价值的数
  3. 从高位到低位，将该位的所有1都分配给前若干个数
  4. 计算这k个构造出的数的平方和

具体实现时，我们可以统计每个比特位上1的个数，然后贪心地将高位的比特优先分配给前面的数，这样能确保前k个数尽可能大。

代码实现

class Solution {
public:
    int maxSum(vector<int>& nums, int k) {
        const int MOD = 1e9 + 7;
        vector<int> bitCount(30, 0);
        
        // 统计每个比特位上1的个数
        for (int num : nums) {
            for (int i = 0; i < 30; i++) {
                if (num & (1 << i)) {
                    bitCount[i]++;
                }
            }
        }
        
        vector<long long> result(k, 0);
        
        // 贪心分配比特位
        for (int i = 29; i >= 0; i--) {
            int ones = bitCount[i];
            for (int j = 0; j < k && ones > 0; j++) {
                result[j] |= (1LL << i);
                ones--;
            }
        }
        
        long long sum = 0;
        for (int i = 0; i < k; i++) {
            sum = (sum + (result[i] * result[i]) % MOD) % MOD;
        }
        
        return sum;
    }
};

class Solution:
    def maxSum(self, nums: List[int], k: int) -> int:
        MOD = 10**9 + 7
        bit_count = [0] * 30
        
        # 统计每个比特位上1的个数
        for num in nums:
            for i in range(30):
                if num & (1 << i):
                    bit_count[i] += 1
        
        result = [0] * k
        
        # 贪心分配比特位
        for i in range(29, -1, -1):
            ones = bit_count[i]
            for j in range(k):
                if ones > 0:
                    result[j] |= (1 << i)
                    ones -= 1
        
        total = 0
        for num in result:
            total = (total + num * num) % MOD
        
        return total

public class Solution {
    public int MaxSum(IList<int> nums, int k) {
        const int MOD = 1000000007;
        int[] bitCount = new int[30];
        
        // 统计每个比特位上1的个数
        foreach (int num in nums) {
            for (int i = 0; i < 30; i++) {
                if ((num & (1 << i)) != 0) {
                    bitCount[i]++;
                }
            }
        }
        
        long[] result = new long[k];
        
        // 贪心分配比特位
        for (int i = 29; i >= 0; i--) {
            int ones = bitCount[i];
            for (int j = 0; j < k && ones > 0; j++) {
                result[j] |= (1L << i);
                ones--;
            }
        }
        
        long sum = 0;
        for (int i = 0; i < k; i++) {
            sum = (sum + (result[i] * result[i]) % MOD) % MOD;
        }
        
        return (int)sum;
    }
}

var maxSum = function(nums, k) {
    const MOD = 1e9 + 7;
    const bitCount = new Array(30).fill(0);
    
    // 统计每个比特位上1的个数
    for (const num of nums) {
        for (let i = 0; i < 30; i++) {
            if (num & (1 << i)) {
                bitCount[i]++;
            }
        }
    }
    
    const result = new Array(k).fill(0);
    
    // 贪心分配比特位
    for (let i = 29; i >= 0; i--) {
        let ones = bitCount[i];
        for (let j = 0; j < k && ones > 0; j++) {
            result[j] |= (1 << i);
            ones--;
        }
    }
    
    let sum = 0;
    for (let i = 0; i < k; i++) {
        sum = (sum + (result[i] * result[i]) % MOD) % MOD;
    }
    
    return sum;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度分析
时间复杂度O(30 × n + 30 × k) = O(n + k)，其中 n 是数组长度。统计比特位需要 O(30n)，分配比特位需要 O(30k)
空间复杂度O(k + 30) = O(k)，需要存储 k 个结果数字和 30 个比特位计数

相关题目