淘先锋技术网

首页 1 2 3 4 5 6 7

今天主要想分享的是自己在面试过程中遇见的一道面试题,是一道简单的算法题。

在面试的过程中,我使用了 hash 表来解决的(时间复杂度和空间复杂度都是O(n)),但是面试官不满意,当时也实在没想到别的解法。

后来在慢慢的使用位运算的过程中,发现通过位运算,可以让时间复杂度为O(n),空间复杂度为O(1)的解法。那么先看下题目吧。

一、面试题目

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

例子:输入: [4,1,2,1,2]
输出:   4

二、常规解法

看见这道题的第一个想到的就是 hash 表,看下面代码,思路很简单

class Solution {
    public int singleNumber(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        for (Integer i : nums) {
            Integer count = map.get(i);
            count = count == null ? 1 : ++count;
            map.put(i, count);
        }
        for (Integer i : map.keySet()) {
            Integer count = map.get(i);
            if (count == 1) {
                return i;
            }
        }
        return -1; // 未找到
    }
}

这个思路就很简单,不过时间复杂度和空间复杂度都是O(n)。

其思想:

  1. 第一个 for 循环遍历一次,然后以 num 为 key,num 出现的次数作为 value,存入 map 中。

  2. 然后第二个 for 循环遍历一次,次数出现为1的就是只出现一次的那个数。

  3. 否则返回-1,表示未找到。

思路很清晰很简单,但是面试官不满意呀。

三、位运算

这道题使用的就是异或^这个位运算符。那么^的原理是什么了?

异或^:它可以对两个数的比特位进行比较。然后返回一些新的数。当2个操作数的对应位不相同时,该数的对应位就为1。

不好理解哈,看下图。

比如20(二进制表示为:00010100)和17(二进制表示为:00010001)进行异或,得到的值为5。将2个数的二进制进行比较,相同则为0,不相同则为1。

那这道题用异或的解法怎么写了?代码如下:

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

这样的解法的时间复杂度为O(n),空间复杂度为O(1)。确实很强。

关于为什么异或这样写可以解决这道题,我将官网的证明 copy 过来了,如下:

首先:
异或有一下3个性质:
任何数和 0 做异或运算,结果仍然是原来的数,即a^0 = 0
任何数和其自身做异或运算,结果是 0,即 a^a = 0
异或运算满足交换律和结合律,即 a^b^a = a^a^b = 0^b = 0

为什么使用异或可以解这道题,证明如下 :

四:总结

有些知识平常使用起来不是很多,但是有的时候这些不常用的知识却有着更高的解题效率。

因为我们写的代码最后都会转换成二进制在底层进行运行,所以位运算还是很有用的,比如求一个数的一半,我们平常会这么些num = num/2,学了位运算后,可以使用右移运算符num = num >> 1。右移一位等价于除以2。

欢迎关注【无量测试之道】公众号,回复【领取资源】

Python+Unittest框架API自动化、

Python+Unittest框架API自动化、

Python+Pytest框架API自动化、

Python+Pandas+Pyecharts大数据分析、

Python+Selenium框架Web的UI自动化、

Python+Appium框架APP的UI自动化、

Python编程学习资源干货、

资源和代码 免费送啦~
文章下方有公众号二维码,可直接微信扫一扫关注即可。

备注:我的个人公众号已正式开通,致力于IT互联网技术的分享。

包含:数据分析、大数据、机器学习、测试开发、API接口自动化、测试运维、UI自动化、性能测试、代码检测、编程技术等。

微信搜索公众号:“无量测试之道”,或扫描下方二维码:

在这里插入图片描述

添加关注,让我们一起共同成长!