Java

  • /**
    
     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];
            }
        }
    }
    
  • // 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(object):
        def singleNonDuplicate(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            return reduce(lambda x, y: x^y, nums)
    

Java

  • 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];
        }
    }
    
  • // 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(object):
        def singleNonDuplicate(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            return reduce(lambda x, y: x^y, nums)
    

All Problems

All Solutions