Leetcode-136-只出现一次的数字

Leecode-136-Single Number

思路：异或

题目描述

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

注意：不能使用额外的空间

Solution：异或

• 如果没有时间复杂度和空间复杂度的限制，这道题有很多种解法

• 不能使用额外的空间：使用位运算

对于这道题，可使用异或运算XOR。异或运算有以下三个性质。

• 任何数字和0做异或运算，结果仍然是原来的数字，即 a⊕0=a。

• 任何数字和自己做异或运算，结果是0，即 a⊕a=0。

• 异或运算满足结合律和交换律。

a⊕b⊕a=b⊕a⊕a=b⊕(a⊕a)=b⊕0=b。

举例描述：[参考力扣官方题解][https://leetcode-cn.com/problems/single-number/solution/zhi-chu-xian-yi-ci-de-shu-zi-by-leetcode-solution/]

1. 任何数字和0做异或运算，结果仍然是原来的数字

2. 任何数字和自己做异或运算，结果是0

3. 异或运算满足结合律和交换律

Java

Solution :

// 异或解决
// 1. 一个数异或本身得0
// 2. 异或满足结合律和交换律

class Solution {
    public int singleNumber(int[] nums) {
        int n = nums.length;

        // 拿第一个数 依次异或 后面的数
        for (int i = 1; i < n; i++) {
            nums[0] ^= nums[i];
        }

        // 返回异或的结果
        return nums[0];
    }
}

• 时间复杂度： O（n） 遍历一遍数组
• 空间复杂度： O（1） 没有使用额外的空间

Python

Solution :

打赏