0%

[Leetcode]136. Single Number(C++)

题目描述

题目链接: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,最后剩下的一个数就是不重复的数。代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
#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