找出强数对的最大异或值 I
难度:
标签:
题目描述
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 = [5,6,25,30]
Output: 7
Explanation: There are 6 strong pairs in the array nums: (5, 5), (5, 6), (6, 6), (25, 25), (25, 30) and (30, 30).
The maximum XOR possible from these pairs is 25 XOR 30 = 7 since the only other non-zero XOR value is 5 XOR 6 = 3.
Constraints:
1 <= nums.length <= 501 <= nums[i] <= 100
代码结果
运行时间: 36 ms, 内存: 16.1 MB
/*
* Solution Idea:
* - Use Java Streams to find all strong pairs in the array nums.
* - Calculate the XOR value for each strong pair.
* - Find the maximum XOR value among all strong pairs using Stream operations.
*/
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
public class StrongPairsStream {
public static int findMaxXOR(int[] nums) {
List<Integer> numList = Arrays.stream(nums).boxed().collect(Collectors.toList());
return numList.stream()
.flatMap(x -> numList.stream().map(y -> new int[]{x, y}))
.filter(pair -> Math.abs(pair[0] - pair[1]) <= Math.min(pair[0], pair[1]))
.mapToInt(pair -> pair[0] ^ pair[1])
.max()
.orElse(0);
}
public static void main(String[] args) {
int[] nums1 = {1, 2, 3, 4, 5};
System.out.println(findMaxXOR(nums1)); // Output: 7
int[] nums2 = {10, 100};
System.out.println(findMaxXOR(nums2)); // Output: 0
int[] nums3 = {5, 6, 25, 30};
System.out.println(findMaxXOR(nums3)); // Output: 7
}
}解释
方法:
这个题解采用了基于贪心和位操作的优化策略来找到最大的异或值。首先，数组按非递减顺序排序。算法从最高位（high_bit）开始尝试构建最大的异或值。通过不断增加掩码（mask），算法尝试增加当前位的值（通过或运算），然后使用字典d来存储已经探索的y值与掩码的结果。对于每个y值，检查是否存在一个前面的x值，使得x与y的异或结果新的尝试值new_ans，并且满足强数对的条件。如果找到，则更新ans为new_ans，这意味着在当前位设置为1的情况下找到了符合条件的最大异或值。
时间复杂度:
O(n * log(max(nums)))
空间复杂度:
O(n)
代码细节讲解
🦆
在题解中，为什么首先需要对数组进行排序？这一步骤对后续的算法实现有什么重要性？
▷🦆
排序后如何保证在尝试新的异或值`new_ans`时，所找到的强数对仍然符合条件`|x - y| <= min(x, y)`？
▷🦆
题解中提到使用掩码`mask`来逐位构建可能的最大异或值，这种方法的有效性是基于什么原理？
▷