【EASY】Single Number

发布于: 2019-04-02 23:18
阅读: 59
评论: 0
喜欢: 0

问题

原题链接:https://leetcode.com/problems/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

分析过程

  • 输入:一个整数数组,所有数字都出现了两次,只有一个数字出现了一次。
  • 输出:找到这个只出现了一次的数。
  • 思路:任何数,自己按位异或自己都是 0,因此只要循环异或,剩下的数就是要找的数。

解决方法

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int result = 0;
        for (int num : nums) {
            result ^= num;
        }
        return result;
    }
};

Thanks for reading.

All the best wishes for you! 💕