河南专业网站建设公司排名,莲都区建设局网站,做积分网站,网站页面设计收费新年第一篇文章#xff0c;先祝大家新年快乐#xff01;#xff01;那么接下来进入正文。 前言 前阵子突发奇想#xff0c;突然开始刷leetcode。其中刷到了一道有意思的题目#xff0c;发现这道题是当时秋招的时候#xff0c;腾讯面试官曾经问过我的题目。于是分享给大家…新年第一篇文章先祝大家新年快乐那么接下来进入正文。 前言 前阵子突发奇想突然开始刷leetcode。其中刷到了一道有意思的题目发现这道题是当时秋招的时候腾讯面试官曾经问过我的题目。于是分享给大家看下。 题目描述 给定一个非空整数数组除了某个元素只出现一次以外其余每个元素均出现两次。找出那个只出现了一次的元素。 初步解法 这道题第一眼看过去思路挺简单的我们只需要维护一个对象来记录每一个元素出现的次数使用元素的值作为key,元素出现的次数作为value。之后再遍历这个对象找到value为1的key。对应的key就是那个元素。代码如下:
function singleNumber(nums) {const obj {};for (let i 0; i lt; 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和任何一个数字异或呢结果是数字本身。 我们举个栗子 假设我们有一个数组里面元素为[a, a, c, c, b, b, d]。那么我们对数组里的所有元素进行按位异或操作即a ^ a ^ c ^ c ^ b ^ b ^ d,是不是就等价于0 ^ 0 ^ 0 ^ d d。而d就是数组里只出现一次的元素。 那么我们可以扩展一下对于任意满足某个元素只出现一次以外其余每个元素均出现两次的数组是不是可以通过这种方式来得到那个只出现一次的元素。 这样一来的话我们是不是有了这个问题的解决办法了我们只需要遍历数组将所有的值取异或最终剩下的值就是那个只出现一次的数字。代码如下
/*** 只存在一次的数字* 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 lt; nums.length; i) {nums[0] ^ nums[i];}return nums[0];
};console.log(singleNumber([2, 2, 1, 4, 4, 5, 5, 1, 8])); 结语 这道面试题主要考验面试者对异或的理解以及能不能活学活用将这道题与异或联系在一起。当然最重要的还是多学习、多刷题、多看书。这样才能不断进步。 本文地址在-本人博客地址, 欢迎给个 start 或 follow 来源https://segmentfault.com/a/1190000017756829 转载于:https://www.cnblogs.com/qixidi/p/10224705.html
