Simple, recursive Golang solution (6ms)


  • 0
    D
    func singleNonDuplicate(nums []int) int {
        piv := pickPiv(nums)
        return singleRecur(nums, piv)
    }
    
    func pickPiv(nums []int) int {
        if len(nums) < 3 {
            return 0;
        }
        piv := int(len(nums) / 2)
        //if we pick a pivot between a pair, increment. 
        //We don't want to split the array between pairs.
        if nums[piv] == nums[piv+1] {
            return piv+1;
        } else {
            return piv;
        }
    }
    
    func singleRecur(nums []int, piv int) int {
        if len(nums) == 0 {
            return 0;
        }
        if len(nums) < 3 {
            return nums[0];
        }
        //this is our base case of three numbers. There are three possibilities:
        //a) [2,1,1] in this case, nums[0] is our non-dup
        //b) [1,1,2] in this case, nums[2] is our non-dup
        //c) [1,2,3] in this case, nums[1] is between two other pairs, so nums[1] is our non-dup.
        //For example, the full array for case (c) might look like this: [1,1,2,3,3]
        if len(nums) == 3 {
            if nums[1] == nums[2] {
                return nums[0];
            } else if nums[1] == nums[0] {
                return nums[2];
            } else {
                return nums[1];
            }
        }
        left := nums[:piv+1]
        right := nums[piv+1:]
        //since a side without duplications contains only pairs, its length is a multiple of two.
        //Therefore, whichever side has an odd length must contain our non-dup.
        if len(left) % 2 != 0 {
            piv = pickPiv(left)
            return singleRecur(left, piv)
        } else {
            piv = pickPiv(right) 
            return singleRecur(right, piv)
        }
    }
    

Log in to reply
 

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