Welcome to Subscribe On Youtube
  • /**
    
     Given a sorted array consisting of only integers where every element appears twice except for one element which appears once. Find this single element that appears only once.
    
     Example 1:
     Input: [1,1,2,3,3,4,4,8,8]
     Output: 2
    
     Example 2:
     Input: [3,3,7,7,10,11,11]
     Output: 10
    
     Note: Your solution should run in O(log n) time and O(1) space.
    
     */
    
    public class Single_Element_in_a_Sorted_Array {
    
        class Solution {
            public int singleNonDuplicate(int[] nums) {
    
                if (nums == null || nums.length == 0) {
                    return -1;
                }
    
                int start = 0, end = nums.length - 1;
    
                while (start < end) {
                    // We want the first element of the middle pair,
                    // which should be at an even index if the left part is sorted.
                    // Example:
                    // Index: 0 1 2 3 4 5 6
                    // Array: 1 1 3 3 4 8 8
                    //            ^
                    int mid = (start + end) / 2;
                    if (mid % 2 == 1) mid--;
    
                    // We didn't find a pair. The single element must be on the left.
                    // (pipes mean start & end)
                    // Example: |0 1 1 3 3 6 6|
                    //               ^ ^
                    // Next:    |0 1 1|3 3 6 6
                    if (nums[mid] != nums[mid + 1]) end = mid;
    
                        // We found a pair. The single element must be on the right.
                        // Example: |1 1 3 3 5 6 6|
                        //               ^ ^
                        // Next:     1 1 3 3|5 6 6|
                    else start = mid + 2;
                }
    
                // 'start' should always be at the beginning of a pair.
                // When 'start > end', start must be the single element.
                return nums[start];
            }
        }
    }
    
    ############
    
    class Solution {
        public int singleNonDuplicate(int[] nums) {
            int left = 0, right = nums.length - 1;
            while (left < right) {
                int mid = (left + right) >> 1;
                // if ((mid % 2 == 0 && nums[mid] != nums[mid + 1]) || (mid % 2 == 1 && nums[mid] !=
                // nums[mid - 1])) {
                if (nums[mid] != nums[mid ^ 1]) {
                    right = mid;
                } else {
                    left = mid + 1;
                }
            }
            return nums[left];
        }
    }
    
  • // OJ: https://leetcode.com/problems/single-element-in-a-sorted-array/
    // Time: O(logN)
    // Space: O(1)
    class Solution {
    public:
        int singleNonDuplicate(vector<int>& A) {
            int L = 0, R = A.size() - 1;
            while (L < R) {
                int M = (L + R) / 2;
                if ((M % 2 == 0 && A[M] == A[M + 1])
                   || (M % 2 == 1 && A[M] == A[M - 1])) L = M + 1;
                    else R = M;
            }
            return A[L];
        }
    };
    
  • class Solution:
        def singleNonDuplicate(self, nums: List[int]) -> int:
            left, right = 0, len(nums) - 1
            while left < right:
                mid = (left + right) >> 1
                # Equals to: if (mid % 2 == 0 and nums[mid] != nums[mid + 1]) or (mid % 2 == 1 and nums[mid] != nums[mid - 1]):
                if nums[mid] != nums[mid ^ 1]:
                    right = mid
                else:
                    left = mid + 1
            return nums[left]
    
    ############
    
    class Solution(object):
        def singleNonDuplicate(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            return reduce(lambda x, y: x^y, nums)
    
  • func singleNonDuplicate(nums []int) int {
    	left, right := 0, len(nums)-1
    	for left < right {
    		mid := (left + right) >> 1
    		if nums[mid] != nums[mid^1] {
    			right = mid
    		} else {
    			left = mid + 1
    		}
    	}
    	return nums[left]
    }
    
  • function singleNonDuplicate(nums: number[]): number {
        let left = 0,
            right = nums.length - 1;
        while (left < right) {
            const mid = (left + right) >> 1;
            if (nums[mid] != nums[mid ^ 1]) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return nums[left];
    }
    
    
  • impl Solution {
        pub fn single_non_duplicate(nums: Vec<i32>) -> i32 {
            let mut l = 0;
            let mut r = nums.len() - 1;
            while l < r {
                let mid = l + r >> 1;
                if nums[mid] == nums[mid ^ 1] {
                    l = mid + 1;
                } else {
                    r = mid;
                }
            }
            nums[l]
        }
    }
    
    
  • class Solution {
        public int singleNonDuplicate(int[] nums) {
            int low = 0, high = nums.length - 1;
            while (low < high) {
                if (high - low == 1) {
                    if (low == 0)
                        return nums[low];
                    else if (high == nums.length - 1)
                        return nums[high];
                }
                int mid = (high - low) / 2 + low;
                int num = nums[mid];
                if (num != nums[mid - 1] && num != nums[mid + 1])
                    return num;
                else {
                    if (mid % 2 == 0 && num == nums[mid + 1] || mid % 2 == 1 && num == nums[mid - 1])
                        low = mid + 1;
                    else
                        high = mid - 1;
                }
            }
            return nums[low];
        }
    }
    
    ############
    
    class Solution {
        public int singleNonDuplicate(int[] nums) {
            int left = 0, right = nums.length - 1;
            while (left < right) {
                int mid = (left + right) >> 1;
                // if ((mid % 2 == 0 && nums[mid] != nums[mid + 1]) || (mid % 2 == 1 && nums[mid] !=
                // nums[mid - 1])) {
                if (nums[mid] != nums[mid ^ 1]) {
                    right = mid;
                } else {
                    left = mid + 1;
                }
            }
            return nums[left];
        }
    }
    
  • // OJ: https://leetcode.com/problems/single-element-in-a-sorted-array/
    // Time: O(logN)
    // Space: O(1)
    class Solution {
    public:
        int singleNonDuplicate(vector<int>& A) {
            int L = 0, R = A.size() - 1;
            while (L < R) {
                int M = (L + R) / 2;
                if ((M % 2 == 0 && A[M] == A[M + 1])
                   || (M % 2 == 1 && A[M] == A[M - 1])) L = M + 1;
                    else R = M;
            }
            return A[L];
        }
    };
    
  • class Solution:
        def singleNonDuplicate(self, nums: List[int]) -> int:
            left, right = 0, len(nums) - 1
            while left < right:
                mid = (left + right) >> 1
                # Equals to: if (mid % 2 == 0 and nums[mid] != nums[mid + 1]) or (mid % 2 == 1 and nums[mid] != nums[mid - 1]):
                if nums[mid] != nums[mid ^ 1]:
                    right = mid
                else:
                    left = mid + 1
            return nums[left]
    
    ############
    
    class Solution(object):
        def singleNonDuplicate(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            return reduce(lambda x, y: x^y, nums)
    
  • func singleNonDuplicate(nums []int) int {
    	left, right := 0, len(nums)-1
    	for left < right {
    		mid := (left + right) >> 1
    		if nums[mid] != nums[mid^1] {
    			right = mid
    		} else {
    			left = mid + 1
    		}
    	}
    	return nums[left]
    }
    
  • function singleNonDuplicate(nums: number[]): number {
        let left = 0,
            right = nums.length - 1;
        while (left < right) {
            const mid = (left + right) >> 1;
            if (nums[mid] != nums[mid ^ 1]) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return nums[left];
    }
    
    
  • impl Solution {
        pub fn single_non_duplicate(nums: Vec<i32>) -> i32 {
            let mut l = 0;
            let mut r = nums.len() - 1;
            while l < r {
                let mid = l + r >> 1;
                if nums[mid] == nums[mid ^ 1] {
                    l = mid + 1;
                } else {
                    r = mid;
                }
            }
            nums[l]
        }
    }
    
    

All Problems

All Solutions