前言:

leetcode前前后后刷了几遍,一直没有坚持下来。这次决定坚持一下,立个flag,一年刷350道题

题目:

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

说明:

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

示例 1:

输入: [2,2,1]

输出: 1

示例 2:

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

输出: 4

思路:

这道题可以用位运算中的异或来解决:

    1. 一个数异或同一个数两次,得到的还是本身,即:a^b^b = a
    2. 任何数和0求异或都是其本身

(异或的运算规则:a^a = 0 a^b = 1)

java:

class Solution {
     public int singleNumber(int[] nums) {
        int res = 0;
        for (int num : nums){
            res ^= num;
        }
        return res;
    }
}

执行结果:

python3:

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        res = 0
        for num in nums:
            res ^= num
        return res

执行结果:

01-13 08:28