04月27, 2019

只出现一次的数字

题目描述

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

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗?

示例 1:

输入: [2,2,1]

输出: 1

示例 2:

输入: [4,1,2,1,2]

输出: 4

思路

  1. 快慢指针法,以count记录当前元素的个数,若一遍循环后,count为1,则停止返回当前元素
  2. 异或

异或的性质

1) 满足交换律:A^B = B^A

2) 满足结合律:(A^B)^C = A^(B^C)

3) 0^A = A

4) A^A = 0

nums数组的各元素为a1,a2,...an;

0^a1^a2^...^an=b

b为只出现一次的数

代码:

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

本文链接:https://lyuly.com/post/leetcode136.html

-- EOF --

Comments

评论加载中...

注:如果长时间无法加载,请针对 disq.us | disquscdn.com | disqus.com 启用代理。