算法——只出现一次的数字

2019年7月10日 0 条评论 15 次阅读 0 人点赞

来源

leetcode 第 136 号问题,经典面试题

题目

给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。

解法思路

暴力?那还谈什么算法。。。我们的算法可以做到线性时间复杂度而且不使用额外空间。解题前我说说几个点,如下:

  • 异或运算 ^
  • 异或运算遵循交换律 a^b^c = a^c^b = b^c^a = ...
  • 异或运算的特点
    • a^a = 0
    • a^0 = a

看完这几个点,这道题也就解决了,思路便是把数组内所有元素都进行异或,结果便是那个只出现一次的元素。

参考代码

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ans = 0;
        for(int i = 0; i < nums.size(); i++)
            ans ^= nums[i];
        return ans;
    }
};
头像

didi

这个人太懒什么东西都没留下

文章评论(0)