LeetCode 540. A single element in an ordered array

540. A single element in an ordered array

Give you an ordered array of integers only , Each of these elements will appear twice , Only one number will appear once .

Please find and return the number that only appears once .

The solution you design must meet O(log n) Time complexity and O(1) Spatial complexity .

Example 1:

 Input : nums = [1,1,2,3,3,4,4,8,8]
 Output : 2

Example 2:

 Input : nums =  [3,3,7,7,10,11,11]
 Output : 10

Tips :

• 1 <= nums.length <= 105
• 0 <= nums[i] <= 105

Two 、 Method 1

Pure XOR

class Solution {
    
    public int singleNonDuplicate(int[] nums) {
    
        int res = 0;
        for (int num : nums) {
    
            res ^= num;
        }
        return res;
    }
}

Complexity analysis

• Time complexity ：O(n).

• Spatial complexity ：O(1).

Two 、 Method 1

Two points + Exclusive or

class Solution {
    
    public int singleNonDuplicate(int[] nums) {
    
        int l = 0;
        int r = nums.length - 1;
        while (l < r) {
    
            int mid = l + ((r - l) >> 1);
            if (nums[mid] == nums[mid ^ 1]) {
    
                l = mid + 1;
            } else {
    
                r = mid;
            }
        }
        return nums[l];
    }
}

Complexity analysis

• Time complexity ：O(logn), among n It's an array nums The length of . You need to binary search in the range of the whole array , The time complexity of binary search is O(logn).

• Spatial complexity ：O(1).