设为首页 | 加入收藏

欢迎访问9号彩票网是否真实_9号彩票最新官方网站_9号彩票网

中心动态 >> 鱼油-图解 LeetCode 第 421 题:数组中两个数的最大异或值



今日共享的标题来源于 LeetCode 第 421 号问题:数组中两个数的最大异或值。在 异或 这个知识点里边归于一个中高难度的标题。

标题描绘

给定一个非空数组,数组中元素为 a0, a1, a2, … , an-1,其间 0 ≤ ai < 231

找到 ai 和 aj 最大的异或 (XOR) 运算成果,其间0 ≤ i, j < n 。

你能在 O(n) 的时刻处理这个问题吗?

示例:

输入: [3, 10, 5, 25, 2, 8]
输出: 28
解说: 最大的成果是 5 ^ 25 = 28.

标题解析

处理这个问题,咱们首要需求运用异或运算的一个性质:

假如 a ^ b = c 建立,那么a ^ c = b 与 b ^ c = a 均建立。

假如有三个数,满意其间两个数的异或值等于另一个值,那么这三个数的次序能够恣意互换

  • 那么怎么了解这个性质呢?由于异或运算其实便是二进制下不进位的加法,你无妨自己举几个比如,在草稿纸上验证一下。

那这个性质怎么应用到本题呢?

这道题找最大值的思路是这样的:由于两两异或能够得到一个值,在一切的两两异或得到的值中,必定有一个最大值,咱们估测这个最大值应该是什么样的?即根据“最大值”的存在性解题(必定存在)。在这儿要着重一下:

咱们只用关怀这个最大的异或值需求满意什么性质,从而推出这个最大值是什么,而不用关怀这个异或值是由哪两个数得来的。

(上面这句话很重要,假如读者一开端看不了解下面的考虑,无妨多看几遍我上面写的这句话。)

所以有如下考虑:

1、二进制下,咱们期望一个数尽可能大,即期望越高位上越能够呈现“1”,这样这个数便是所求的最大数,这是贪心算法的思维。

2、所以,咱们能够从最高位开端,到最低位,首要假定高位是 “1”,把这 n 个数悉数遍历一遍,看看这一位是不是真的能够是“1”,不然这一位就得是“0”,判别的根据是上面“异或运算的性质”,即下面的第 3 点;

3、假如 a ^ b = max 建立 ,max 表明当时得到的“最大值”,那么必定有 max ^ b = a 建立。咱们能够先假定当时数位上的值为 “1”,再把当时得到的数与这个 n 个数的 前缀(由所以从高位到低位看,所以称为“前缀”)进行异或运算,放在一个哈希表中,再顺次把一切 前缀 与这个假定的“最大值”进行异或今后得到的成果放到哈希表里查询一下,假如查得到,就阐明这个数位上能够是“1”,不然就只能是 0(看起来很晕,能够看代码了解)。

一种极点的状况是,这 n 个数在某一个数位上悉数是 0 ,那么恣意两个数异或今后都只能是 0,那么假定当时数位是 1 这件工作就不建立。

4、怎么得到前缀,能够用掩码(mask),掩码能够进行如下结构,将掩码与原数顺次进行“与”运算,就能得到前缀。

10000000000000000000000000000000
1100000000000000鱼油-图解 LeetCode 第 421 题:数组中两个数的最大异或值0000000000000000
11100000000000000000000000000000
11110000000000000000000000000000
11111000000000000000000000000000
11111100000000000000000000000000
11111110000000000000000000000000
11111111000000000000000000000000
11111111100000000000000000000000
11111111110000000000000000000000
11111111111000000000000000000000
11111111111100000000000000000000
11111111111110000000000000000000
11111111111111000000000000000000
11111111111111100000000000000000
11111111111111110000000000000000
11111111111111111000000000000000
11111111111111111100000000鱼油-图解 LeetCode 第 421 题:数组中两个数的最大异或值000000
11111111111111111110000000000000
11111111111111111111000000000000
11111111111111111111100000000000
11111111111111111111110000000000
11111111111111111111111000000000
11111111111111111111111100000000
11111111111111111111111110000000
11111111111111111111111111000000
11111111111111111111111111100000
11111111111111111111111111110000
11111111111111111111111111111000
11111111111111111111111111111100
11111111111111111111111111111110
11111180岁巨型娃娃鱼11111111111111111111111111

以标题中的数组 [3, 10, 5, 25, 2, 8] 为例,下面解说这个最大的两两异或值是怎么得到的,这儿为了便利演示,只展现一个数二进制的低 8 位。

图片演示

LeetCode 第 421 题:数组中两个数的最大异或值-1

LeetCode 第 421 题:数组中两个数的最大异或值-2

LeetCode 第 421 题:数组中两个数的最大异或值-3

LeetCode 第 421 题:数组中两个数的最大异或值-4

LeetCode 第 421 题:数组中两个数的最大异或值-5

LeetCode鱼油-图解 LeetCode 第 421 题:数组中两个数的最大异或值 第 421 题:数组中两个数的最大异或值-6

代码完成

Python 代码:

class Solution:
def findMaximumXOR(self, nums: List[int]) -> int:
res = 0
mask = 0
for i in range(31, -1, -1):
mask |= (1 << i)
# 当时得到的一切前缀都放在这个哈希表中
s = set()
for num in nums:
s.add(mask & num)
# 先“贪心肠”假定这个数位上是 “1” ,假如悉数前缀都看完,都不契合条件,这个数位上便是 “0”
temp = res | (1 << i)
for prefix in s:
if temp ^ prefix in s:
res = temp
break
return res

Java 代码:

import java.util.HashSet;
import java.util.Set;
public class Solution {
// 先确认高位,再确认低位(有点贪心算法的意思),才干确保这道题的最大性质
// 一位接着一位去确认这个数位的巨细
// 运用性质:a ^ b = c ,则 a ^ c = b,且 b ^ c = a
public int findMaximumXOR(int[] nums) {
int res鱼油-图解 LeetCode 第 421 题:数组中两个数的最大异或值 = 0;
int mask = 0;
for (int i = 31; i >= 0; i--) {
// 留意点1:留意保存前缀的办法,mask 是这样得来的
// 用异或也是能够的 mask = mask ^ (1 << i);
mask = mask | (1 << i);
// System.out.println(Integer.toBinaryString(mask));
Set set = new HashSet<>();
for (int num : nums) {
// 留意点2:这儿运用 & ,保存前缀的意思(从高位到低位)
set.add(num & mask);
}
// 这儿先假定第 n 位为 1 ,前 n-1 位 res 为之前迭代求得
int temp = res | (1 << i);
for (Integer prefix : set) {
if (set.contains(prefix ^ temp)) {
res = temp;
break;
}
}
}
return res;
}
public static void main(String[] args) {
int[] nums = {3, 10, 5, 25, 2, 8};
Solution2 solution2 = new Solution2();
int maximumXOR = solution2.findMaximumXOR(nums);
System.out.println(maximumXOR);
}
}

复杂度剖析

  • 时刻复杂度:(),把整个数组看了 32次,即 (32)=()。
  • 空间复杂度:(1),运用了一个哈希表,这个哈希表最多存 32 个前缀,(32)=(1)。




上一条      下一条
返回顶部