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.
思路:很简单,既然按递增顺序排列,比乱序好做的多,因为重复的数字总是相邻,用增量法即可解.由于只有一个数出现单次,其余均出现两次,观察易知单次的数必出现在偶数下标(数组从0开始),因此用一个计数器求和,遍历数组,下标为奇则取元素负值,累加;下标为偶则取元素正值,累加.
最终求和结果就是只出现一次的数.
int singleNonDuplicate(vector<int>& nums) {
int sum = 0; //求和
for (int i = 0; i < nums.size(); i++) {
if (i%2 == 0) sum += nums[i]; //下标为偶,加之(取正值)
else sum -= nums[i]; //下标为奇,减之(取负值)
}
return sum;
}
