关闭

一道有意思的面试算法题

时间: 2019-01-05阅读: 1374标签: 算法

前言

前阵子突发奇想,突然开始刷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


站长推荐

1.云服务推荐: 国内主流云服务商,各类云产品的最新活动,优惠券领取。地址:阿里云腾讯云华为云

2.广告联盟: 整理了目前主流的广告联盟平台,如果你有流量,可以作为参考选择适合你的平台点击进入

链接: http://www.fly63.com/article/detial/1773

关闭

JS 洗牌算法

最近的一个塔罗牌项目中,有一个洗牌的需求,其实也就是随机打乱数组,遂网上搜了下,再此做个整理…塔罗牌,举例来说,我们有一个如下图所示的数组,数组长度为 9,数组内元素的值顺次分别是 1~9:

js实现:在字符串中找出第一个只出现一次的字符

在给出一个字符串,找出第一个只出现一次的字符。思路分析:可以用对象保存字符出现的次数。将值删除,用 indexOf 查找还有没有相同字符,并查找之前删过的字符,indexOf 的第二个参数,从当前值往后搜索,并查找之前已经查过的字符

JS常见算法题目

JS常见算法题目:xiaoshuo-ss-sfff-fe 变为驼峰xiaoshuoSsSfffFe、数组去重、统计字符串中出现最多的字母、字符串反序、深拷贝、合并多个有序数组、约瑟夫环问题

Tracking.js_ js人脸识别前端代码/算法框架

racking.js 是一个独立的JavaScript库,实现多人同时检测人脸并将区域限定范围内的人脸标识出来,并保存为图片格式,跟踪的数据既可以是颜色,也可以是人,也就是说我们可以通过检测到某特定颜色,或者检测一个人体/脸的出现与移动,来触发JavaScript 事件。

JS算法之深度优先遍历(DFS)和广度优先遍历(BFS)

在开发页面的时候,我们有时候会遇到这种需求:在页面某个dom节点中遍历,找到目标dom节点,我们正常做法是利用选择器document.getElementById(),document.getElementsByName()或者document.getElementsByTagName(),

程序员必知必会的10 大基础算法!

快速排序算法:快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序n个项目要Ο(nlogn)次比较。在最坏状况下则需要Ο(n2)次比较,但这种状况并不常见。事实上,快速排序通常明显比其他Ο(nlogn)算法更快

原生Js获取数组中最长的连续数字序列的方法

给定一个无序的整数序列, 找最长的连续数字序列。例如:给定[100, 4, 200, 1, 3, 2],最长的连续数字序列是[1, 2, 3, 4]。此方法不会改变传入的数组,会返回一个包含最大序列的新数组。

Js算法:计算两数之和

给出两个 非空 的链表用来表示两个非负的整数。其中,它们各自的位数是按照 逆序 的方式存储的,并且它们的每个节点只能存储 一位 数字。如果,我们将这两个数相加起来,则会返回一个新的链表来表示它们的和

为什么我认为数据结构与算法对前端开发很重要?

一个具有层级结构的数据,实现这个功能非常容易,因为这个结构和组件的结构是一致的,递归遍历就可以了。但是,由于后端通常采用的是关系型数据库,所以返回的数据通常会是这个样子:前端这边想要将数据转换一下其实也不难,因为要合并重复项

RSA算法详解

这篇文章主要是针对一种最常见的非对称加密算法——RSA算法进行讲解。其实也就是对私钥和公钥产生的一种方式进行描述,RSA算法的核心就是欧拉定理,根据它我们才能得到私钥,从而保证整个通信的安全。

点击更多...

内容以共享、参考、研究为目的,不存在任何商业目的。其版权属原作者所有,如有侵权或违规,请与小编联系!情况属实本人将予以删除!