找出强数对的最大异或值 II

You are given a 0-indexed integer array nums. A pair of integers x and y is called a strong pair if it satisfies the condition:

• |x - y| <= min(x, y)

You need to select two integers from nums such that they form a strong pair and their bitwise XOR is the maximum among all strong pairs in the array.

Return the maximum XOR value out of all possible strong pairs in the array nums.

Note that you can pick the same integer twice to form a pair.

 

Example 1:

Input: nums = [1,2,3,4,5]
Output: 7
Explanation: There are 11 strong pairs in the array nums: (1, 1), (1, 2), (2, 2), (2, 3), (2, 4), (3, 3), (3, 4), (3, 5), (4, 4), (4, 5) and (5, 5).
The maximum XOR possible from these pairs is 3 XOR 4 = 7.

Example 2:

Input: nums = [10,100]
Output: 0
Explanation: There are 2 strong pairs in the array nums: (10, 10) and (100, 100).
The maximum XOR possible from these pairs is 10 XOR 10 = 0 since the pair (100, 100) also gives 100 XOR 100 = 0.

Example 3:

Input: nums = [500,520,2500,3000]
Output: 1020
Explanation: There are 6 strong pairs in the array nums: (500, 500), (500, 520), (520, 520), (2500, 2500), (2500, 3000) and (3000, 3000).
The maximum XOR possible from these pairs is 500 XOR 520 = 1020 since the only other non-zero XOR value is 2500 XOR 3000 = 636.

 

Constraints:

• 1 <= nums.length <= 5 * 104
• 1 <= nums[i] <= 220 - 1

/*
题目思路：
1. 使用Java Stream API，首先生成所有可能的强数对。
2. 计算每个强数对的异或值。
3. 找出异或值的最大值。
*/

import java.util.*;
import java.util.stream.*;

public class Solution {
    public int maxStrongPairXOR(int[] nums) {
        return IntStream.range(0, nums.length)
                .boxed()
                .flatMap(i -> IntStream.range(i, nums.length)
                        .filter(j -> Math.abs(nums[i] - nums[j]) <= Math.min(nums[i], nums[j]))
                        .mapToObj(j -> nums[i] ^ nums[j]))
                .max(Integer::compareTo)
                .orElse(0);
    }
}

此题解采用了排序和位操作的方法来寻找最大的异或值。首先，对数组进行排序以便后续的二分查找。主要的策略是从最高位开始尝试设置当前异或结果的每一位（从高到低），检查是否存在有效的强数对能够支持这一位的设置。使用一个辅助函数highestBit来确定最大数值的最高有效位。然后在此位上，从后向前遍历数组，对于每个数，确定其潜在的强数对区间，并使用二分查找在有效区间内寻找合适的强数对。若找到，则更新当前最大异或值ans并缩小后续搜索的范围。

O(n log n)

O(n)