返回

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

#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

Built with Hugo
Theme Stack designed by Jimmy