Hard

题目描述

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

如果满足下述条件，则数对 (num1, num2) 是 优秀数对：

  • num1 和 num2 都 在数组 nums 中存在。
  • num1 OR num2 和 num1 AND num2 的二进制表示中设置位数之和大于等于 k，其中 OR 是按位 或 操作，而 AND 是按位 与 操作。

返回 不同 优秀数对的数目。

对于两个数对 (a, b) 和 (c, d)，如果 a != c 或者 b != d，则认为它们是不同的。例如，(1, 2) 和 (2, 1) 是不同的。

注意：如果 num1 == num2 且你在数组中至少找到 一次 num1，则数对 (num1, num2) 也可以是优秀数对。

示例 1：

输入：nums = [1,2,3,1], k = 3
输出：5
解释：优秀数对有以下几个：
- (3, 3)：(3 AND 3) 和 (3 OR 3) 都等于 (11) 。设置位数之和是 2 + 2 = 4 ≥ k = 3 。
- (2, 3) 和 (3, 2)：(2 AND 3) 等于 (10) ，(2 OR 3) 等于 (11) 。设置位数之和是 1 + 2 = 3 。
- (1, 3) 和 (3, 1)：(1 AND 3) 等于 (01) ，(1 OR 3) 等于 (11) 。设置位数之和是 1 + 2 = 3 。
所以优秀数对的数目是 5 。

示例 2：

输入：nums = [5,1,1], k = 10
输出：0
解释：该数组中不存在优秀数对。

提示：

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

解题思路

解题思路

这道题的关键在于理解题目提示中的重要性质：num1 OR num2 和 num1 AND num2 的设置位数之和等于 num1 和 num2 的设置位数之和。

数学证明： 对于任意两个数的某一位：

  • 如果两个数该位都是1：OR结果为1，AND结果为1，贡献2个设置位
  • 如果一个数该位是1，另一个是0：OR结果为1，AND结果为0，贡献1个设置位
  • 如果两个数该位都是0：OR结果为0，AND结果为0，贡献0个设置位

因此，popcount(a OR b) + popcount(a AND b) = popcount(a) + popcount(b)。

算法步骤：

  1. 去重：由于我们只关心数值及其设置位数，相同的数只需要保留一个
  2. 统计每个数的设置位数，并按设置位数分组计数
  3. 对于每对设置位数组合，如果它们的和 ≥ k，则计算对应的数对数量
  4. 使用双指针或二分查找优化匹配过程

时间复杂度优化：

  • 朴素方法：O(n²)枚举所有数对
  • 优化方法：按设置位数分组后，使用双指针在O(log n)时间内处理，总复杂度O(n log n)

代码实现

class Solution {
public:
    long long countExcellentPairs(vector<int>& nums, int k) {
        // 去重并统计每个数的设置位数
        unordered_set<int> unique_nums(nums.begin(), nums.end());
        vector<int> bit_counts;
        
        for (int num : unique_nums) {
            bit_counts.push_back(__builtin_popcount(num));
        }
        
        sort(bit_counts.begin(), bit_counts.end());
        
        long long result = 0;
        int n = bit_counts.size();
        
        // 双指针法
        for (int i = 0; i < n; i++) {
            // 找到第一个满足 bit_counts[i] + bit_counts[j] >= k 的位置
            int target = k - bit_counts[i];
            int j = lower_bound(bit_counts.begin(), bit_counts.end(), target) - bit_counts.begin();
            
            // 从位置j开始的所有元素都满足条件
            result += n - j;
        }
        
        return result;
    }
};

class Solution:
    def countExcellentPairs(self, nums: List[int], k: int) -> int:
        # 去重并统计每个数的设置位数
        unique_nums = set(nums)
        bit_counts = [bin(num).count('1') for num in unique_nums]
        bit_counts.sort()
        
        result = 0
        n = len(bit_counts)
        
        # 双指针法
        for i in range(n):
            # 使用二分查找找到第一个满足条件的位置
            target = k - bit_counts[i]
            j = bisect.bisect_left(bit_counts, target)
            
            # 从位置j开始的所有元素都满足条件
            result += n - j
        
        return result

public class Solution {
    public long CountExcellentPairs(int[] nums, int k) {
        // 去重并统计每个数的设置位数
        var uniqueNums = new HashSet<int>(nums);
        var bitCounts = new List<int>();
        
        foreach (int num in uniqueNums) {
            bitCounts.Add(PopCount(num));
        }
        
        bitCounts.Sort();
        
        long result = 0;
        int n = bitCounts.Count;
        
        // 双指针法
        for (int i = 0; i < n; i++) {
            // 二分查找第一个满足条件的位置
            int target = k - bitCounts[i];
            int j = BinarySearch(bitCounts, target);
            
            // 从位置j开始的所有元素都满足条件
            result += n - j;
        }
        
        return result;
    }
    
    private int PopCount(int num) {
        int count = 0;
        while (num > 0) {
            count += num & 1;
            num >>= 1;
        }
        return count;
    }
    
    private int BinarySearch(List<int> arr, int target) {
        int left = 0, right = arr.Count;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] >= target) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
}

var countExcellentPairs = function(nums, k) {
    // 去重并统计每个数的设置位数
    const uniqueNums = [...new Set(nums)];
    const bitCounts = uniqueNums.map(num => {
        return num.toString(2).split('1').length - 1;
    });
    
    bitCounts.sort((a, b) => a - b);
    
    let result = 0;
    const n = bitCounts.length;
    
    // 双指针法
    for (let i = 0; i < n; i++) {
        // 二分查找第一个满足条件的位置
        const target = k - bitCounts[i];
        let j = binarySearch(bitCounts, target);
        
        // 从位置j开始的所有元素都满足条件
        result += n - j;
    }
    
    return result;
    
    function binarySearch(arr, target) {
        let left = 0, right = arr.length;
        while (left < right) {
            const mid = Math.floor((left + right) / 2);
            if (arr[mid] >= target) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度分析
时间复杂度O(n log n)
空间复杂度O(n)

详细分析：

  • 去重操作：O(n)
  • 计算设置位数：O(n × log(max_value))，其中log(max_value)约为32
  • 排序：O(n log n)
  • 双指针遍历和二分查找：O(n log n)
  • 总时间复杂度：O(n log n)
  • 空间复杂度主要用于存储去重后的数组和设置位数组：O(n)

相关题目