Java O(nlogn) solution greedy


  • 0
    D

    From the most significant bit to the least significant bit, try to find two numbers with different bit value in that position. During this process, divide numbers into two groups, and do it recursively. Since we care about the bit value from most significant to least significant position, this is an intuitive greedy solution.

    public class Solution {
        public int findMaximumXOR(int[] nums) {
            if (nums == null || nums.length == 0) {
                return 0;
            }
            List<Integer> list = new ArrayList<>();
            for (int num : nums) {
                list.add(num);
            }
            for (int mask = (1 << 30); mask != 0; mask >>= 1) {
                List<Integer> one = new ArrayList<>();
                List<Integer> zero = new ArrayList<>();
                divide(list, mask, one, zero);
                if (one.size() > 0 && zero.size() > 0) {
                    return mask + findMaximumXOR(one, zero, mask >> 1);
                }
            }
            return 0;
        }
    
        private int findMaximumXOR(List<Integer> one, List<Integer> zero, int mask) {
            if (mask == 0) {
                return 0;
            }
            List<Integer> oneone = new ArrayList<>();
            List<Integer> onezero = new ArrayList<>();
            divide(one, mask, oneone, onezero);
            List<Integer> zeroone = new ArrayList<>();
            List<Integer> zerozero = new ArrayList<>();
            divide(zero, mask, zeroone, zerozero);
            int ret = 0;
            boolean goodcase = false;
            if (oneone.size() > 0 && zerozero.size() > 0) {
                goodcase = true;
                ret = Math.max(ret, mask + findMaximumXOR(oneone, zerozero, mask >> 1));
            }
            if (onezero.size() > 0 && zeroone.size() > 0) {
                goodcase = true;
                ret = Math.max(ret, mask + findMaximumXOR(onezero, zeroone, mask >> 1));
            }
            if (!goodcase) {
                if (oneone.size() > 0) {
                    ret = findMaximumXOR(oneone, zeroone, mask >> 1);
                } else {
                    ret = findMaximumXOR(onezero, zerozero, mask >> 1);
                }
            }
            return ret;
        }
    
        private void divide(List<Integer> nums, int mask, List<Integer> one, List<Integer> zero) {
            for (int num : nums) {
                if ((num & mask) != 0) {
                    one.add(num);
                } else {
                    zero.add(num);
                }
            }
        }
    }
    

Log in to reply
 

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