[LeetCode] Maximum XOR of Two Numbers in an Array 数组中异或值最大的两个数字

简介:

Given a non-empty array of numbers, a0, a1, a2, … , an-1, where 0 ≤ ai < 231.

Find the maximum result of ai XOR aj, where 0 ≤ ij < n.

Could you do this in O(n) runtime?

Example:

Input: [3, 10, 5, 25, 2, 8]
Output: 28
Explanation: The maximum result is 5 ^ 25 = 28.

这道题是一道典型的位操作Bit Manipulation的题目,我开始以为异或值最大的两个数一定包括数组的最大值,但是OJ给了另一个例子{10,23,20,18,28},这个数组的异或最大值是10和20异或,得到30。那么只能另辟蹊径,正确的做法是按位遍历,题目中给定了数字的返回不会超过231,那么最多只能有32位,我们用一个从左往右的mask,用来提取数字的前缀,然后将其都存入set中,我们用一个变量t,用来验证当前位为1再或上之前结果res,看结果和set中的前缀异或之后在不在set中,这里用到了一个性质,若a^b=c,那么a=b^c,因为t是我们要验证的当前最大值,所以我们遍历set中的数时,和t异或后的结果仍在set中,说明两个前缀可以异或出t的值,所以我们更新res为t,继续遍历,如果上述讲解不容易理解,那么建议自己带个例子一步一步试试,并把每次循环中set中所有的数字都打印出来,基本应该就能理解了,参见代码如下:

class Solution {
public:
    int findMaximumXOR(vector<int>& nums) {
        int res = 0, mask = 0;
        for (int i = 31; i >= 0; --i) {
            mask |= (1 << i);
            set<int> s;
            for (int num : nums) {
                s.insert(num & mask);
            }
            int t = res | (1 << i);
            for (int prefix : s) {
                if (s.count(t ^ prefix)) {
                    res = t;
                    break;
                }
            }
        }
        return res;
    }
};

本文转自博客园Grandyang的博客,原文链接:数组中异或值最大的两个数字[LeetCode] Maximum XOR of Two Numbers in an Array ,如需转载请自行联系原博主。

目录
打赏
0
0
0
0
5351
分享
相关文章
JavaScript中通过array.map()实现数据转换、创建派生数组、异步数据流处理、复杂API请求、DOM操作、搜索和过滤等,array.map()的使用详解(附实际应用代码)
array.map()可以用来数据转换、创建派生数组、应用函数、链式调用、异步数据流处理、复杂API请求梳理、提供DOM操作、用来搜索和过滤等,比for好用太多了,主要是写法简单,并且非常直观,并且能提升代码的可读性,也就提升了Long Term代码的可维护性。 只有锻炼思维才能可持续地解决问题,只有思维才是真正值得学习和分享的核心要素。如果这篇博客能给您带来一点帮助,麻烦您点个赞支持一下,还可以收藏起来以备不时之需,有疑问和错误欢迎在评论区指出~
通过array.some()实现权限检查、表单验证、库存管理、内容审查和数据处理;js数组元素检查的方法,some()的使用详解,array.some与array.every的区别(附实际应用代码)
array.some()可以用来权限检查、表单验证、库存管理、内容审查和数据处理等数据校验工作,核心在于利用其短路机制,速度更快,节约性能。 博客不应该只有代码和解决方案,重点应该在于给出解决方案的同时分享思维模式,只有思维才能可持续地解决问题,只有思维才是真正值得学习和分享的核心要素。如果这篇博客能给您带来一点帮助,麻烦您点个赞支持一下,还可以收藏起来以备不时之需,有疑问和错误欢迎在评论区指出~
通过array.every()实现数据验证、权限检查和一致性检查;js数组元素检查的方法,every()的使用详解,array.some与array.every的区别(附实际应用代码)
array.every()可以用来数据验证、权限检查、一致性检查等数据校验工作,核心在于利用其短路机制,速度更快,节约性能。 博客不应该只有代码和解决方案,重点应该在于给出解决方案的同时分享思维模式,只有思维才能可持续地解决问题,只有思维才是真正值得学习和分享的核心要素。如果这篇博客能给您带来一点帮助,麻烦您点个赞支持一下,还可以收藏起来以备不时之需,有疑问和错误欢迎在评论区指出~
别再用双层遍历循环来做新旧数组对比,寻找新增元素了!使用array.includes和Set来提升代码可读性
这类问题的重点在于能不能突破基础思路,突破基础思路是从程序员入门变成中级甚至高级的第一步,如果所有需求都通过最基础的业务逻辑来做,是得不到成长的。 博客不应该只有代码和解决方案,重点应该在于给出解决方案的同时分享思维模式,只有思维才能可持续地解决问题,只有思维才是真正值得学习和分享的核心要素。如果这篇博客能给您带来一点帮助,麻烦您点个赞支持一下,还可以收藏起来以备不时之需,有疑问和错误欢迎在评论区指出~
JavaScript中通过array.filter()实现数组的数据筛选、数据清洗和链式调用,JS中数组过滤器的使用详解(附实际应用代码)
用array.filter()来实现数据筛选、数据清洗和链式调用,相对于for循环更加清晰,语义化强,能显著提升代码的可读性和可维护性。博客不应该只有代码和解决方案,重点应该在于给出解决方案的同时分享思维模式,只有思维才能可持续地解决问题,只有思维才是真正值得学习和分享的核心要素。如果这篇博客能给您带来一点帮助,麻烦您点个赞支持一下,还可以收藏起来以备不时之需,有疑问和错误欢迎在评论区指出~
|
3月前
|
go语言中的数组(Array)
go语言中的数组(Array)
129 67
拿下奇怪的前端报错(一):报错信息是一个看不懂的数字数组Buffer(475) [Uint8Array],让AI大模型帮忙解析
本文介绍了前端开发中遇到的奇怪报错问题,特别是当错误信息不明确时的处理方法。作者分享了自己通过还原代码、试错等方式解决问题的经验,并以一个Vue3+TypeScript项目的构建失败为例,详细解析了如何从错误信息中定位问题,最终通过解读错误信息中的ASCII码找到了具体的错误文件。文章强调了基础知识的重要性,并鼓励读者遇到类似问题时不要慌张,耐心分析。
111 5
Java“(array) <X> Not Initialized” (数组未初始化)错误解决
在Java中,遇到“(array) &lt;X&gt; Not Initialized”(数组未初始化)错误时,表示数组变量已被声明但尚未初始化。解决方法是在使用数组之前,通过指定数组的大小和类型来初始化数组,例如:`int[] arr = new int[5];` 或 `String[] strArr = new String[10];`。
|
5月前
【LeetCode-每日一题】 删除排序数组中的重复项
【LeetCode-每日一题】 删除排序数组中的重复项
41 4
|
5月前
|
Leetcode第三十三题(搜索旋转排序数组)
这篇文章介绍了解决LeetCode第33题“搜索旋转排序数组”的方法,该问题要求在旋转过的升序数组中找到给定目标值的索引,如果存在则返回索引,否则返回-1,文章提供了一个时间复杂度为O(logn)的二分搜索算法实现。
45 0
Leetcode第三十三题(搜索旋转排序数组)

热门文章

最新文章

  • 1
    JavaScript 中通过Array.sort() 实现多字段排序、排序稳定性、随机排序洗牌算法、优化排序性能,JS中排序算法的使用详解(附实际应用代码)
    21
  • 2
    🚀 力扣热题 78:子集(详细解析)
    15
  • 3
    JavaScript中通过array.map()实现数据转换、创建派生数组、异步数据流处理、复杂API请求、DOM操作、搜索和过滤等,array.map()的使用详解(附实际应用代码)
    19
  • 4
    通过array.reduce()实现数据汇总、条件筛选和映射、对象属性的扁平化、转换数据格式、聚合统计、处理树结构数据和性能优化,reduce()的使用详解(附实际应用代码)
    17
  • 5
    多维数组操作,不要再用遍历循环foreach了!来试试数组展平的小妙招!array.flat()用法与array.flatMap() 用法及二者差异详解
    14
  • 6
    深入理解 JavaScript 中的 Array.find() 方法:原理、性能优势与实用案例详解
    23
  • 7
    通过array.some()实现权限检查、表单验证、库存管理、内容审查和数据处理;js数组元素检查的方法,some()的使用详解,array.some与array.every的区别(附实际应用代码)
    16
  • 8
    通过array.every()实现数据验证、权限检查和一致性检查;js数组元素检查的方法,every()的使用详解,array.some与array.every的区别(附实际应用代码)
    12
  • 9
    JavaScript中通过array.filter()实现数组的数据筛选、数据清洗和链式调用,JS中数组过滤器的使用详解(附实际应用代码)
    12
  • 10
    Array.forEach实战详解:简化循环与增强代码可读性;Array.forEach怎么用;面对大量数据时怎么提高Array.forEach的性能
    11