「算法」一道惊艳了我的算法题

起因

最近在 leetcode 上看到了这么一道题，叫 只出现一次的数字，题目要求如下

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

说明：

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

示例 1:
输入: [2,2,1]
输出: 1
示例 2:

输入: [4,1,2,1,2]
输出: 4
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/single-number
著作权归领扣网络所有。

贼菜的解法

看到这个题目的时候觉得，拿个数组遍历一下，如果不存在的就插入数组，如果已经存在的就把它从数组拿出去，最后剩下的那个就是目标

kotlin 实现

fun singleNumber(nums: IntArray): Int {
    var numbers = arrayListOf<Int>()
    for (num in nums) {
        if (numbers.contains(num)) {
            numbers.remove(num)
        } else {
            numbers.add(num)
        }
    }

    return numbers[0]
}

但是这样解法的空间复杂度是 O(n)，时间复杂度 O(n² )，并不是题目要求的 O(1) 直到我看到大神的解法，立马被惊艳到，

大神的解法

大神的解法是这样的

kotlin 实现

class Solution {
    fun singleNumber(nums: IntArray): Int {
        var number = 0;
        for (n in nums) {
            number = n xor number
        }

        return number;
    }
}

只用了一个整形变量 number，时间复杂度 O(n)，空间复杂度 O(1)，是不是很神奇，那么他是怎么做到的呢？最主要的就是这一句

number = n xor number

用到了按位异或运算，这里就要提到异或运算的原理了

异或运算原理

简单异或密码（英语：simple XOR cipher）是密码学中一种简单的加密算法，它按照如下原则进行运算，异或运算记作 oxr：

A xor 0 = A (不同为1)

A xor A = 0 (相同为0)

(A xor B) xor C = A xor (B xor C) (结合律，异或顺序不影响结果)

(B xor A) xor A = B xor 0 = B (对同一个数进行两次相同异或得到原数)

记得小时候学乘法的时候，0 是一个很神奇的数字，0 乘任何数都得 0，而异或运算的 0 刚好相反，0 与任何数异或等于任何数

异或原理被精准的用于这道题，因为数组里只有一个数只出现了一次，其他均出现了两次，利用上面的原理 4，就能把这个数最终找出来，我们举个例子说明

假设数组里有 [1, 2, 3, 4, 5, 3, 4, 1, 2]

期望结果为 5

根据原理3，1 xor 2 xor 3 xor 4 xor 5 xor 3 xor 4 xor 1 xor 2 = (1 xor 1) xor (2 xor 2) xor (3 xor 3 )xor (4 xor 4) xor 5 = 0 xor 0 xor 0 xor 0 xor 0 xor 5 = 5

是不是很厉害呀，今天就到这里吧

0 0 votes

Article Rating