LeetCode 421 Maximum XOR of Two Numbers in an Array 解题报告 - hanzheng992的博客 - CSDN博客
暴力解什么很显然, 可以直接在O(n^2)的时间内进行两两计算, 并且保存最大值, 代码什么的也不说了, 很简单.
Better Solution
对输入的数组, 我们将其中的元素根据最高位的值分为两类, 最高位为0的一类, 最高位为1的一类, 如果两类都不为空, 那么该问题的最终结果一定是从第一类中找一个数和第二类中的一个数进行异或得到的结果.
那么此题就可以优化为, 从两个数列中各取一个数, 求两个数按位异或结果的最大值. 因此, 我们可以设计一个helper函数帮我们处理.
那么, 我们可以根据次高位再将数继续分成两类, 因此, 我们可以得到四个类, arr00, arr01, arr10, arr11. 那么最终的解一定在(arr00, arr11), (arr10, arr01)中; 如果存在空集, 那么最终的解一定在(arr00, arr01), (arr11, arr10)中.
平均时间复杂度分析, 假设O(n)表示helper函数的时间复杂度, 其中n表示传入helper两个数列的总长度. 那么我们有 O(n) = n + 2 * O(n/2), 化简后可得 O(n) = O(n log n) + O(n) = O(n log n)
Read full article from LeetCode 421 Maximum XOR of Two Numbers in an Array 解题报告 - hanzheng992的博客 - CSDN博客
No comments:
Post a Comment