专栏首页陈纪庚一道有意思的面试算法题

一道有意思的面试算法题

新年第一篇文章,先祝大家新年快乐!!那么接下来进入正文。

前言

前阵子突发奇想,突然开始刷leetcode。其中刷到了一道有意思的题目,发现这道题是当时秋招的时候,腾讯面试官曾经问过我的题目。于是分享给大家看下。

题目描述

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

初步解法

这道题第一眼看过去,思路挺简单的,我们只需要维护一个对象来记录每一个元素出现的次数,使用元素的值作为key,元素出现的次数作为value。之后再遍历这个对象,找到value为1的key。对应的key就是那个元素。代码如下:

function singleNumber(nums) {
  const obj = {};
  for (let i = 0; i < nums.length; i++) {
    obj[nums[i]] = obj[nums[i]] ? obj[nums[i]] + 1 : 1;
  }
  for (let key in obj) {
    if (obj[key] === 1) {
      return Number(key); // 由于 key 是 string ,因此我们这里需要转化下
    }
  }
}

console.log(singleNumber([2, 2, 1, 4, 4, 5, 5, 1, 8])); // 8

增加限制

是吧,这道题很简单,那我为什么要说它有意思呢? 因为题目里面其实还有一个限制:

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

重点在于不使用额外空间。我们上面那种解法,创建了一个新的对象来储存结果,明显是不行的。那么有没有办法可以只使用原来的数组来实现这个功能呢?

最终解法

我们可以思考下,一个数组里,所有的数字都出现两次,除了一个我们要找的数字只出现一次。那么,我们有没有办法将两个相同的数字给过滤掉呢?

好啦,不卖关子了,之前有了解过的人应该就知道解决方案了,如果之前没了解过这方面东西的人,可以继续往下看。

解决方案:异或操作

异或运算是对于二进制数字而言的,比如说一个有两个二进制a、b,如果a、b两个值不相同,则异或结果为1。如果a、b两个值相同,异或结果为0。

而javascript的按位异或(即^操作)操作,则会对两个数字相应的每一对比特位执行异或操作。

比如说 1 ^ 2,本质上其实是1和2的每一对比特位执行异或操作,等价于下面

  00000000000000000000000000000001 // 数字1对应的二进制
^ 00000000000000000000000000000010 // 数字2对应的二进制
= 00000000000000000000000000000011 // 数字3对应的二进制

因此1^2的结果就为3啦。

那么如果两个相同的数字进行异或操作,结果就可想而知,答案为0啦。

如果是0和任何一个数字异或呢?结果是数字本身。

这样一来的话,我们是不是有了这个问题的解决办法了?我们只需要遍历数组,将所有的值取异或,最终剩下的值,就是那个只出现一次的数字。代码如下:

/**
 * 只存在一次的数字
 * https://leetcode-cn.com/explore/interview/card/top-interview-questions-easy/1/array/25/
 * @param {number[]} nums
 * @return {number}
 */
function singleNumber(nums) {
  for (let i = 1; i < nums.length; i++) {
    nums[0] ^= nums[i];
  }
  return nums[0];
};

console.log(singleNumber([2, 2, 1, 4, 4, 5, 5, 1, 8]));

结语

这道面试题主要考验面试者对异或的理解,以及能不能活学活用,将这道题与异或联系在一起。当然,最重要的还是多学习、多刷题、多看书。这样才能不断进步。

本文地址在->本人博客地址, 欢迎给个 start 或 follow

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • HTML5 drag和drop的亲手实践

    最近在公司打杂的时候,突然分到了一个锅,就是要支持一个新的功能:用户可以通过拖曳组件来改变组件的顺序。因此,这阵子就看了一下网上的一些drag和drog的文章以...

    嘿嘿嘿
  • SPA初试-1

    即每一个页面对应着一个状态,一个状态有一个状态名,还有一个模板/模板url,这样我们就可以将不同页面的内容写到不同的html里,然后通过templateUrl将...

    嘿嘿嘿
  • javasciprt性能优化

    本文主要是在我读《高性能Javascript》之后,想要记录下一些有用的优化方案,并且就我本身的一些经验,来大家一起分享下,

    嘿嘿嘿
  • # python # # 分形 # Sierpinski Carpet 谢尔宾斯基地毯

    好久没更新,趁着中午休息更新一下, 这次的是分形中的谢尔宾斯基地毯,3阶的地毯是下面这个形状(不是二维码哈☺):

    滚神大人
  • 重识Activity——生命周期详解

    1. 单个Activity生命周期 *  显示状态——onCreate()、onStart()、onResume() * 隐藏状态——onPause():部...

    城市中的游牧民族
  • 视频流媒体平台EasyNVR在防控治安、焚烧治理的案例运用

    焚烧秸秆造成空气污染的事件频频发生,如何充分利用信息化手段实现秸秆禁烧的技术防控,成为了我们国家亟待解决的问题。

    EasyNVR
  • 安卓7.0在线更新解析包时出现问题

    关于7.0行为变更,FileProvider应用共享文件的问题可以看鸿洋大佬的这篇博客 https://blog.csdn.net/lmj623565791/...

    萬物並作吾以觀復
  • LintCode 子数组之和题目分析代码

    给定一个整数数组,找到和为零的子数组。你的代码应该返回满足要求的子数组的起始位置和结束位置

    desperate633
  • jvm 的局部变量表

    Java中方法的局部变量是放在虚拟机栈的局部变量表里面,形参也算一个。本地变量表,就是局部变量表,只是翻译不同。代码说明

    潇洒
  • 应急响应案例:木马清理

    pwnriglhttps.service 存在异常,该木马在6月2日就已经存在了。

    何刚

扫码关注云+社区

领取腾讯云代金券