DAY 8
0
Software Development

## 【Day 8】#136 - Single Number

Given a non-empty 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?

Example 1:

``````Input: [2,2,1]
Output: 1
``````

Example 2:

``````Input: [4,1,2,1,2]
Output: 4
``````

## 解法

``````class Solution {
public int singleNumber(int[] nums) {
int value=0;
for(int i=0;i<nums.length;i++){
value^=nums[i];
}
return value;
}
}
``````

## 備註

Java的位元運算有以下四種：

1. 補數運算(~)：進行數值的2補數運算，如下：
``````     ~  0 1 0 1   運算元1
=  1 0 1 1   (~運算元1)    –    回傳結果
``````
1. AND(&)：若兩者皆為１則輸出為１，否則輸出皆為０，如下：
``````        0 0 1 1   運算元1
AND  1 0 0 1   運算元2
=  0 0 0 1   (運算元1 & 運算元2)    –    回傳結果
``````
1. OR(|)：若兩者有一個為１則輸出為１，兩者皆為０則輸出為０，如下：
``````        0 0 1 1   運算元1
OR  1 0 0 1   運算元2
=  1 0 1 1   (運算元1 | 運算元2)    –    回傳結果
``````
1. XOR(^)：若兩者位元不同則輸出為１，若相同則輸出為０，如下：
``````        0 0 1 1   運算元1
XOR  1 0 0 1   運算元2
=  1 0 1 0   (運算元1 ^ 運算元2)    –    回傳結果
``````

LeetCode小試身手14