136. Single Number
Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.
You must implement a solution with a linear runtime complexity and use only constant extra space.
Example 1:
Example 2:
Example 3:
Constraints:
- 1 < = n u m s . l e n g t h < = 3 ∗ 1 0 4 1 <= nums.length <= 3 * 10^4 1<=nums.length<=3∗104
- − 3 ∗ 1 0 4 < = n u m s [ i ] < = 3 ∗ 1 0 4 -3 * 10^4 <= nums[i] <= 3 * 10^4 −3∗104<=nums[i]<=3∗104
- Each element in the array appears twice except for one element which appears only once.
From: LeetCode
Link: 136. Single Number
Solution:
Ideas：
- We initialize result to 0.
- We iterate through the nums array using a for loop.
- For each element in nums, we perform an XOR operation with result.
- Since XOR of a number with itself is 0, and XOR of a number with 0 is the number itself, all elements appearing twice will cancel out.
- The remaining number, which appears only once, will be the final value of result.
- Finally, we return result, which is the single number in the array.
Code:
int singleNumber(int* nums, int numsSize) {
int result = 0;
for (int i = 0; i < numsSize; i++) {
result ^= nums[i];
}
return result;
}