百度360必应搜狗淘宝本站头条
当前位置:网站首页 > 文章教程 > 正文

神奇的位运算

xsobi 2024-11-23 10:50 1 浏览

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

在面试的过程中,我使用了 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。

相关推荐

js向对象中添加元素(对象,数组) js对象里面添加元素

一、添加一个元素对象名["属性名"]=值(值:可以是一个值,可以是一个对象,也可以是一个数组)这样添加进去的元素,就是一个值或对象或数组...

JS小技巧,如何去重对象数组?(一)

大家好,关于数组对象去重的业务场景,想必大家都遇到过类似的需求吧,这对这样的需求你是怎么做的呢。下面我就先和大家分享下如果是基于对象的1个属性是怎么去重实现的。方法一:使用.filter()和....

「C/C++」之数组、vector对象和array对象的比较

数组学习过C语言的,对数组应该都不会陌生,于是这里就不再对数组进行展开介绍。模板类vector模板类vector类似于string,也是一种动态数组。能够在运行阶段设置vector对象的长度,可以在末...

如何用sessionStorage保存对象和数组

背景:在工作中,我将[{},{}]对象数组形式,存储到sessionStorage,然后ta变成了我看不懂的形式,然后我想取之用之,发现不可能了~记录这次深刻的教训。$clickCouponIndex...

JavaScript Array 对象 javascript的array对象

Array对象Array对象用于在变量中存储多个值:varcars=["Saab","Volvo","BMW"];第一个数组元素的索引值为0,第二个索引值为1,以此类推。更多有...

JavaScript中的数组Array(对象) js array数组

1:数组Array:-数组也是一个对象-数组也是用来存储数据的-和object不同,数组中可以存储一组有序的数据,-数组中存储的数据我们称其为元素(element)-数组中的每一个元素都有一...

数组和对象方法&amp;数组去重 数组去重的5种方法前端

列举一下JavaScript数组和对象有哪些原生方法?数组:arr.concat(arr1,arr2,arrn);--合并两个或多个数组。此方法不会修改原有数组,而是返回一个新数组...

C++ 类如何定义对象数组?初始化数组?linux C++第43讲

对象数组学过C语言的读者对数组的概念应该很熟悉了。数组的元素可以是int类型的变量,例如int...

ElasticSearch第六篇:复合数据类型-数组,对象

在ElasticSearch中,使用JSON结构来存储数据,一个Key/Value对是JSON的一个字段,而Value可以是基础数据类型,也可以是数组,文档(也叫对象),或文档数组,因此,每个JSON...

第58条:区分数组对象和类数组对象

示例设想有两个不同类的API。第一个是位向量:有序的位集合varbits=newBitVector;bits.enable(4);bits.enable([1,3,8,17]);b...

八皇后问题解法(Common Lisp实现)

如何才能在一张国际象棋的棋盘上摆上八个皇后而不致使她们互相威胁呢?这个著名的问题可以方便地通过一种树搜索方法来解决。首先,我们需要写一个函数来判断棋盘上的两个皇后是否互相威协。在国际象棋中,皇后可以沿...

visual lisp修改颜色的模板函数 怎么更改visual studio的配色

(defunBF-yansemokuai(tuyuanyanse/ss)...

用中望CAD加载LISP程序技巧 中望cad2015怎么加载燕秀

1、首先请加载lisp程序,加载方法如下:在菜单栏选择工具——加载应用程序——添加,选择lisp程序然后加载,然后选择添加到启动组。2、然后是添加自定义栏以及图标,方法如下(以...

图的深度优先搜索和广度优先搜索(Common Lisp实现)

为了便于描述,本文中的图指的是下图所示的无向图。搜索指:搜索从S到F的一条路径。若存在,则以表的形式返回路径;若不存在,则返回nil。...

两个有助于理解Common Lisp宏的例子

在Lisp中,函数和数据具有相同的形式。这是Lisp语言的一个重大特色。一个Lisp函数可以分析另一个Lisp函数;甚至可以和另一个Lisp函数组成一个整体,并加以利用。Lisp的宏,是实现上述特色的...