Single NumberI
分析：這道題應(yīng)該是很簡(jiǎn)單了，直接使用異或運(yùn)算，把重復(fù)出現(xiàn)的數(shù)字消掉剩下的就是出現(xiàn)一次的元素
重慶分公司
重慶分公司
lass Solution {
public int singleNumber(int[] nums) {
int tmp = nums[0];
for(int i = 1;i < nums.length;i++){
tmp = tmp ^ nums[i];
}
return tmp;
}
}Single NumberII
分析：這種題型可以歸納為一個(gè)數(shù)組中的元素某一元素只出現(xiàn)了K次，而其他元素均出現(xiàn)了M次，然后求出出現(xiàn)K次的元素問(wèn)題。如果K
為奇數(shù)M為偶數(shù)，就跟上面第一題是一樣的處理方式了；而其他情況則需要考慮使用位運(yùn)算。我們知道，每個(gè)數(shù)字的二進(jìn)制表示是一定的，所以我們通過(guò)計(jì)算每一位中1的個(gè)數(shù)，然后除3，若余數(shù)為0說(shuō)明該位上為1的數(shù)都出現(xiàn)了三次，若余數(shù)不為0，說(shuō)明我們要找的那個(gè)數(shù)字該位為1，通過(guò)移位運(yùn)算實(shí)現(xiàn)上述過(guò)程。同理，若題目要求其他元素均出現(xiàn)了5次，就除5。
class Solution {
public int singleNumber(int[] nums) {
int ans = 0;
for(int i = 0 ; i < 32 ; i++){
int sum = 0;
for(int j = 0 ; j < nums.length ; j++){
if(((nums[j] >> i) & 1) == 1 ){
sum++;
sum %= 3;
}
}
if(sum != 0){
ans |= sum << i;//將循環(huán)中右移的位移回原位置
}
}
return ans;
}Single NumberIII
分析：數(shù)組中的無(wú)關(guān)元素出現(xiàn)了偶數(shù)次，所以先考慮用異或?qū)⑺鼈兿?，得?和5的異或結(jié)果。然后我們考慮如何將3和5分離：3（011）和5（101）異或的結(jié)果為6(110),我們需要先找到3和5的二進(jìn)制表示中不相同的一位，這里的方法就是6與-6進(jìn)行相與，即110與其補(bǔ)碼(取反加一)011相與，得到010（即從右往左3和5的第二位不同），我們姑且將它稱(chēng)為分離因子。然后遍歷整個(gè)數(shù)組，每個(gè)數(shù)與該分離因子相與可將數(shù)組分為&x==0和&x!=0的兩組，然后在每組內(nèi)部進(jìn)行異或運(yùn)算，得到結(jié)果。
class Solution {
public int[] singleNumber(int[] nums) {
int diff = 0;
for(int num : nums) {
diff ^= num;
}
diff &= -diff;
int[] res = new int[]{0,0};
for(int i : nums) {
if((diff & i) == 0) {
res[0] ^= i;
}
if((diff & i) != 0) {
res[1] ^= i;
}
}
return res;
}
}創(chuàng)新互聯(lián)www.cdcxhl.cn，專(zhuān)業(yè)提供香港、美國(guó)云服務(wù)器，動(dòng)態(tài)BGP最優(yōu)骨干路由自動(dòng)選擇，持續(xù)穩(wěn)定高效的網(wǎng)絡(luò)助力業(yè)務(wù)部署。公司持有工信部辦法的idc、isp許可證， 機(jī)房獨(dú)有T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確進(jìn)行流量調(diào)度，確保服務(wù)器高可用性。佳節(jié)活動(dòng)現(xiàn)已開(kāi)啟，新人活動(dòng)云服務(wù)器買(mǎi)多久送多久。
