O(log n) In-place Recursive Java Solution


  • 0
    C

    public class Solution {

    public int singleNonDuplicate(int[] nums) {
        if (nums.length == 1) {
            return nums[0];
        }
    
        if (nums.length == 3) {
            if (nums[0] < nums[1] && nums[1] < nums[2]) {
                return nums[1];
            } else if (nums[0] == nums[1] && nums[1] < nums[2]) {
                return nums[2];
            } else {
                return nums[0];
            }
        }
    
    
        // length greater than 3...   ex. 5, 7, 9, ....
    
        int startIndex = 0;
        int endIndex = nums.length - 1;
        int midIndex = nums.length / 2;
    
    
        return findSingle(startIndex, endIndex, nums);
    
    
    }
    
    public static int findSingle(int startIndex, int endIndex, int[] nums) {
    
        int currentLength = endIndex - startIndex + 1;
        int midIndex = (startIndex + endIndex) / 2;
    
        if (currentLength == 3) {
            if (nums[midIndex - 1] < nums[midIndex] && nums[midIndex] < nums[midIndex + 1]) {
                return nums[midIndex];
            } else if (nums[midIndex - 1] == nums[midIndex] && nums[midIndex] < nums[midIndex + 1]) {
                return nums[midIndex + 1];
            } else {
                return nums[midIndex - 1];
            }
        }
    
        // currentLength > 3
    
        if (midIndex % 2 == 0) {    // odd remain
    
            if (nums[midIndex - 1] == nums[midIndex] && nums[midIndex] < nums[midIndex + 1]) {  // turn left
                return findSingle(startIndex, midIndex, nums);
            } else if (nums[midIndex - 1] < nums[midIndex] && nums[midIndex] == nums[midIndex + 1]) {   // turn right
                return findSingle(midIndex, endIndex, nums);
            } else {
                return nums[midIndex];
            }
    
        } else {    // even remain
    
            if (nums[midIndex - 1] == nums[midIndex] && nums[midIndex] < nums[midIndex + 1]) {  // turn right
                return findSingle(midIndex + 1, endIndex, nums);
            } else if (nums[midIndex - 1] < nums[midIndex] && nums[midIndex] == nums[midIndex + 1]) {   // turn left
                return findSingle(startIndex, midIndex - 1, nums);
            } else {
                return nums[midIndex];      // impossible ?
            }
    
        }
    
    }
    

    }


Log in to reply
 

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