Non-binary search. O(nlogn) Java solution in 7ms. Study and gain insight!


  • 0
    E
    public class Solution {
        public int findDuplicate(int[] nums) {
            int width = Integer.bitCount((Integer.highestOneBit(nums.length - 1) << 1) - 1);
            int t = 1;
            int ans = 0;
            for (int i = 0; i < width; i++) {
                t *= 2;
                int fullBlocks = nums.length / t;
                int ideal1s = nums.length - (fullBlocks * t / 2 + Math.min(t / 2, nums.length - fullBlocks * t));
                int count1 = 0;
                for (int j = 0; j < nums.length; j++)
                    if ((nums[j] & 1 << i) != 0)
                        count1++;
                if (count1 > ideal1s) {// more 1s than necessary
                    ans |= 1 << i;
                }
            }
            return ans;
        }
    }

Log in to reply
 

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