C++ bitwise iteration, with search space pre-elimination and search direction optimization


  • 1
    A

    Based on @tangx668 's idea.
    But skip those bits that are unanimous to all input numbers. And search from alternate ends to get quicker match if there is one.

    27 / 27 test cases passed
    Status: Accepted
    Runtime: 258 ms

    class Solution {
    public:
        int findMaximumXOR(vector<int>& nums) {
            uint e = nums.size();
            if (!e) return 0;
            uint x = 0, m = 0, w = -1;
            for (auto& n : nums) {
                m |= n;
                w &= n;
            }
            m &= ~w;
            unordered_set<uint> s;
            sort(nums.begin(), nums.end());
            for (uint i = 1<<31; i; i >>= 1) {
                if (!(m & i)) continue;
                uint t = x | i;
                for (uint j = 0, k = e-1, d = 0; j <= k; d = !d) {
                    int n = d ? nums[k--] : nums[j++];
                    if (s.count((n & t) ^ t)) {
                        x = t;
                        break;
                    } else s.insert(n & t);
                }
                s.clear();
            }
            return x;
        }
    };
    

  • 0
    T

    can you more explain it ,i dont understand it ,please!


  • -1
    G

    This is a very intelligent solution, but a horrible one to post here. It's a solution that is intended to "show off" rather than to help others understand it.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.