题目描述
题目链接: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.
例子
例子 1
Input:
nums = [2,2,1]
Output:1
例子 2
Input:
nums = [4,1,2,1,2]
Output:4
例子 3
Input:
nums = [1]
Output:1
Follow Up
Note
Constraints
1 <= nums.length <= 3 * 104
-3 * 10^4 <= nums[i] <= 3 * 10^4
- Each element in the array appears twice except for one element which appears only once.
解题思路
根据异或的性质,如果用 0 一直跟数组中的数进行异或,相同的两个数异或会为 0,最后剩下的一个数就是不重复的数。代码如下:
#include <vector>
class Solution {
public:
int singleNumber(std::vector<int>& nums) {
int val = 0;
for (int num : nums) {
val ^= num;
}
return val;
}
};
- 时间复杂度:
O(n)
- 空间复杂度:
O(1)
GitHub 代码同步地址: 136.SingleNumber.cpp
其他题目: GitHub: Leetcode-C++-Solution 博客: Leetcode-Solutions