136 SingleNumber
Given an array of integers, every element appears twice except for one. Find that single one.
Note:Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
這個(gè)問題很經(jīng)典，變體也多匈辱。
最容易想到的做法肯定是開一個(gè)HashMap存每個(gè)數(shù)字出現(xiàn)的次數(shù)食店。
但是要求是O(n)的復(fù)雜度昨忆，沒有額外的空間開銷或南。
其實(shí)自己想很難想到，看了題解之后大多數(shù)人的感覺是還有這種操作苛败？
就是用一個(gè)0和每個(gè)元素取異或恼五，一個(gè)數(shù)異或自己為0，所以出現(xiàn)兩次的數(shù)異或之后為0阱穗，而出現(xiàn)一次的數(shù)則保留了下來饭冬。
看代碼：
public int singleNumber(int[] nums) {
int i = 0;
for (int num : nums) {
i ^= num;
}
return i;
}
137 Single Number II
LeetCode很有意思，出了1之后可能還有2揪阶，3都是變體昌抠，難度會(huì)增加，有時(shí)候思路完全不一樣鲁僚。
Given an array of integers, every element appears three times except for one, which appears exactly once. Find that single one.
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
這個(gè)說實(shí)話也是很難想到的炊苫，但是還是基于的位運(yùn)算裁厅。
給出discuss中第一名的答案：
public int singleNumber(int[] A) {
int ones = 0, twos = 0;
for(int i = 0; i < A.length; i++){
ones = (ones ^ A[i]) & ~twos;
twos = (twos ^ A[i]) & ~ones;
}
return ones;
}
這個(gè)解法斟酌一下，大致思路就是：
一個(gè)數(shù)出現(xiàn)第一次的時(shí)候存在ones中侨艾，出現(xiàn)第二次的時(shí)候存在twos中执虹，出現(xiàn)第三次的時(shí)候在ones中被清0。所以最后保留的就是出現(xiàn)一次的數(shù)唠梨。
- Single Element in a Sorted Array
上面一題其實(shí)已經(jīng)很枯燥了袋励，不過這一題很有意思。
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.
給出一個(gè)已經(jīng)排序過的數(shù)組当叭，除了一個(gè)數(shù)只出現(xiàn)了一次茬故，其他的數(shù)都出現(xiàn)了兩次。
其實(shí)用137題的寫法也是可以的蚁鳖。
但是我們浪費(fèi)了它已經(jīng)排序過這個(gè)條件了磺芭。
再看看復(fù)雜度給的是O(lgn)
很容易想到的是二分。
public int singleNonDuplicate(int[] nums) {
int left = 0;
int right = nums.length / 2;
while (left < right) {
int mid = left + (right - left)/2;
if (nums[mid * 2] == nums[mid * 2 + 1]) {
left = mid+1;
}
else {
right = mid;
}
}
return nums[left * 2];
}
