Single Number
今天是一道有關(guān)位運(yùn)算的題目纠俭，來(lái)自LeetCode(#136)雄可，難度為Medium乌助，Acceptance為46.5%呻率。
這類題目不需要太多的算法知識(shí)躏将，需要的知識(shí)位運(yùn)算的基礎(chǔ)知識(shí)和經(jīng)驗(yàn)锄弱。
題目如下
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 ?
解題思路及代碼見閱讀原文
思路如下
其實(shí)，該題的思路較為簡(jiǎn)單祸憋，只要想到使用位運(yùn)算就很容易想到会宪。題目中除一個(gè)數(shù)之外，其他數(shù)字都出現(xiàn)兩次蚯窥，可以想到兩個(gè)相同的數(shù)做異或得到了掸鹅，這樣將所有的數(shù)做異或就可以得到那個(gè)只出現(xiàn)一次的數(shù)塞帐。
代碼如下
java版
public class Solution {
/**
*@param A : an integer array
*return : a integer
*/
public int singleNumber(int[] A) {
int ans = 0;
for(int i : A)
ans ^= i;
return ans;
}
}
c++版
int singleNumber(int A[], int n) {
int result = 0;
for (int i = 0; i<n; i++) {
result ^=A[i];
}
return result;
}
