Problem:
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:
|
1 2 |
Input: [1,1,2,3,3,4,4,8,8] Output: 2 |
Example 2:
|
1 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.
Idea:
Binary search.
Time complexity: O(logn)
Space complexity: O(1)
Solution:
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
// Author: Huahua // Runtime: 6 ms class Solution { public: int singleNonDuplicate(vector<int>& nums) { int l = 0; int r = nums.size(); while (l < r) { const int m = l + (r - l) / 2; // int n = m % 2 == 0 ? m + 1 : m - 1; const int n = m ^ 1; if (nums[m] == nums[n]) l = m + 1; else r = m; } return nums[l]; } }; |