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

起因

最近在 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(n2 ),并不是题目要求的 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:

  1. A xor 0 = A (不同为1)
  2. A xor A = 0 (相同为0)
  3. (A xor B) xor C = A xor (B xor C) (结合律,异或顺序不影响结果)
  4. (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 vote
Article Rating
Subscribe
Notify of
guest

This site uses Akismet to reduce spam. Learn how your comment data is processed.

0 Comments
Inline Feedbacks
View all comments