Leetcode[421] Maximum XOR of Two Numbers in an Arr

cocopeak 發(fā)布于2019-08-14 16:37 / 1650人閱讀

摘要：復(fù)雜度思路利用的性質(zhì)，則有，且所以每次從高位開(kāi)始，到某一位為止，所能獲得的最大的數(shù)。設(shè)置變量用來(lái)表示能形成的值，每一次將和其他的相與得到的值加入，表示在當(dāng)前這一位上，數(shù)組里有這么多。

LeetCode[421] 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 ≤ i, j < 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.

BitSet+HashSet

復(fù)雜度
O(N), O(N)

思路
利用XOR的性質(zhì)，a^b = c, 則有 a^c = b，且 b^c = a;
所以每次從高位開(kāi)始，到某一位為止，所能獲得的最大的數(shù)。設(shè)置變量mask用來(lái)表示能形成的值，每一次將mask和其他的num相與得到的值加入set，表示在當(dāng)前這一位上，數(shù)組里有這么多prefix。

假定在某一位上的任意兩數(shù)xor能得到的最大值是tmp,那么他一定滿(mǎn)足a(xor)b = tmp,其中set.contains(a) && set.contains(b). 所以，我們只需要判斷b(xor)tmp的結(jié)果是不是在當(dāng)前這一位下的set內(nèi)，就可以知道這個(gè)tmp能不能又這個(gè)set中的任意兩個(gè)數(shù)組成。

代碼

    public int findMaximumXOR(int[] nums) {
        int max = 0, mask = 0;
        // test each bit pose, 判斷能不能構(gòu)成所需要的值；
        for(int i = 31; i >= 0; i --) {
            // 每次都在之前的基礎(chǔ)上更新mask
            mask = mask | (1 << i);
            Set set = new HashSet<>();
            for(int num : nums) {
                // add the number which has the mask as its prefix;
                set.add(num & mask);
            }
            // 假設(shè)當(dāng)前所能達(dá)到的最大值是這個(gè)temp值；
            int tmp = max | (1 << i);
            for(Integer prefix : set) {
                if(set.contains(prefix ^ tmp)) {
                    // 如果能組成就直接break 
                    max = tmp;
                    break;
                }
            }
        }
        return max;
    }

云服務(wù)器 GPU云服務(wù)器 Numbers Maximum arr LeetCode

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://www.ezyhdfw.cn/yun/66227.html

相關(guān)文章

【7 kyu】Sum of two lowest positive integers

摘要：原題目題目有一個(gè)不少于四個(gè)元素的數(shù)組，計(jì)算其中兩個(gè)最小值的和。對(duì)比我寫(xiě)的方法比較常規(guī)，中采用了的解構(gòu)賦值和箭頭函數(shù) 原題目 Create a function that returns the sum of the two lowest positive numbers given an array of minimum 4 integers. No floats or empty ...

fjcgreat 2019-08-21 16:49 評(píng)論0 收藏0
You need to know curry

Functions are first-class citizen Functions are first-class citizen in JavaScript, as the same as other types(e.g. number, array, object). They can be used as arguments, as well as return value from o...

BigNerdCoding 2019-08-22 15:23 評(píng)論0 收藏0
【LC總結(jié)】K Sum (Two Sum I II/3Sum/4Sum/3Sum Closest)

摘要：找符合條件的總數(shù)。雙指針區(qū)間考慮邊界，長(zhǎng)度，為空，等。之后的范圍用雙指針和表示。若三個(gè)指針的數(shù)字之和為，加入結(jié)果數(shù)組。不要求，所以不用判斷了。同理，頭部?jī)蓚€(gè)指針向后推移，后面建立左右指針夾逼，找到四指針和為目標(biāo)值的元素。 Two Sum Problem Given an array of integers, find two numbers such that they add up ...

awesome23 2019-08-14 15:50 評(píng)論0 收藏0
JavaScript30秒，從入門(mén)到放棄之Array（三）

摘要：否則，直接循環(huán)去拼接該值返回按照指定的方法對(duì)數(shù)組元素進(jìn)行分組歸類(lèi)。使用創(chuàng)建一個(gè)對(duì)象，對(duì)象的鍵是生成的結(jié)果，值是符合該鍵的所有數(shù)組元素組成的數(shù)組。微信公眾號(hào)秒，從入門(mén)到放棄之三原文鏈接：JavaScript30秒，從入門(mén)到放棄之Array（三）水平有限，歡迎批評(píng)指正 flattenDepth Flattens an array up to the specified depth....

FrancisSoung 2019-08-21 18:31 評(píng)論0 收藏0
一次掌握 JavaScript ES5 到 ES8 數(shù)組內(nèi)容

摘要：可選到該位置前停止讀取數(shù)據(jù)，默認(rèn)等于數(shù)組長(zhǎng)度。找出第一個(gè)符合條件的數(shù)組元素，參數(shù)是一個(gè)回調(diào)函數(shù)，所有數(shù)組元素依次執(zhí)行該回調(diào)函數(shù)，直到找出第一個(gè)返回值為的元素，然后返回該元素?；卣{(diào)函數(shù)可以接受三個(gè)參數(shù)，依次為當(dāng)前的值當(dāng)前的位置和原數(shù)組。 ECMAScript 5.1 中提供的數(shù)組方法 ECMA-262/5.1 規(guī)范判斷是否是數(shù)組 Array.isArray ( arg ) // fal...

baiy 2019-08-21 17:29 評(píng)論0 收藏0
JavaScript數(shù)組學(xué)習(xí)記錄_11

摘要：數(shù)組學(xué)習(xí)記錄是的實(shí)例屬性。對(duì)數(shù)組元素進(jìn)行排序，并返回當(dāng)前數(shù)組。返回一個(gè)由所有數(shù)組元素組合而成的字符串。為數(shù)組中的每個(gè)元素執(zhí)行一次回調(diào)函數(shù)。返回一個(gè)數(shù)組迭代器對(duì)象，該迭代器會(huì)包含所有數(shù)組元素的鍵值對(duì)。 JavaScript數(shù)組學(xué)習(xí)記錄 Array.length Array.length 是Array的實(shí)例屬性。返回或設(shè)置一個(gè)數(shù)組中的元素個(gè)數(shù)。該值是一個(gè)無(wú)符號(hào) 32-bit 整數(shù)，并且總是...

TalkingData 2019-08-23 14:10 評(píng)論0 收藏0