Java Solution O(log(n)) time


  • 0
    A
    public class Solution {
        public int singleNonDuplicate(int[] nums) {
            return helper(nums, 0, nums.length-1);
        }
        
        public int helper(int[] nums, int lo, int hi) {
            while(lo <= hi) {
                int mid = (lo+hi)/2;
                if( (mid == 0 || nums[mid] != nums[mid-1]) && (mid == nums.length-1 || nums[mid] != nums[mid+1]) ) return nums[mid];
                if(mid == 0 || nums[mid] == nums[mid-1]) {
                    if(mid%2==0) {
                        hi = mid-1;
                    } else {
                        lo = mid+1;
                    }
                }
                if(mid == nums.length-1 || nums[mid] == nums[mid+1]) {
                    if(mid%2==0) {
                        lo = mid+1;
                    } else {
                        hi = mid-1;
                    }
                }
            }
            return -1;
        }
    }

Log in to reply
 

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