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.
思路:很簡(jiǎn)單,既然按遞增順序排列,比亂序好做的多,因?yàn)橹貜?fù)的數(shù)字總是相鄰,用增量法即可解.由于只有一個(gè)數(shù)出現(xiàn)單次,其余均出現(xiàn)兩次,觀察易知單次的數(shù)必出現(xiàn)在偶數(shù)下標(biāo)(數(shù)組從0開始),因此用一個(gè)計(jì)數(shù)器求和,遍歷數(shù)組,下標(biāo)為奇則取元素負(fù)值,累加;下標(biāo)為偶則取元素正值,累加.
最終求和結(jié)果就是只出現(xiàn)一次的數(shù).
int singleNonDuplicate(vector<int>& nums) {
int sum = 0; //求和
for (int i = 0; i < nums.size(); i++) {
if (i%2 == 0) sum += nums[i]; //下標(biāo)為偶,加之(取正值)
else sum -= nums[i]; //下標(biāo)為奇,減之(取負(fù)值)
}
return sum;
}
