Question
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.
Solution
这个题可以直接对所有元素取一遍异或可以得到答案，但是不满足时间复杂度的要求，log n的要求，明显只能计算一半；因为有一个单出来的，那么这个值所在的那一半肯定有奇数个数字。
Code
class Solution {
public:
int singleNonDuplicate(vector<int>& nums) {
if (nums.size() == 1)
return nums[0];
int middle = nums.size() / 2;
int left = middle - 1;
int right = middle + 1;
if (nums[middle] != nums[left] && nums[middle] != nums[right])
return nums[middle];
if (nums[middle] == nums[left] ) {
if ((middle + 1) & 1 != 0) {
int res = 0;
for (int i = 0; i <= middle; i++)
res = res ^ nums[i];
return res;
} else {
int res = 0;
for (int i = middle + 1; i < nums.size(); i++)
res = res ^ nums[i];
return res;
}
}
if (nums[middle] == nums[right]) {
if ((middle + 1) & 1 != 0) {
int res = 0;
for (int i = middle; i < nums.size(); i++)
res = res ^ nums[i];
return res;
} else {
int res = 0;
for (int i = 0; i < middle; i++)
res = res ^ nums[i];
return res;
}
}
}
};
转载于:https://www.cnblogs.com/zhonghuasong/p/7525677.html
