只出现一次的数字|刷题打卡

吐槽君 分类:javascript

前言

本文正在参与掘金团队号上线活动,点击查看大厂春招职位。

题目

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

说明:

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

示例 1:

输入: [2,2,1]
输出: 1
示例 2:
 

示例 2:

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

题解

题目看着很简单,我们能想到的方法也有很多,但是,题目要求不使用额外空间,具有线性时间复杂度,这个就比较难想到了。

先来说说,如果没有这个限制,我会想到哪些方法?

方法一:利用排序

先利用排序,将数组排序好,然后因为只有一个出现一次的树,所以这个数字必定在奇数位,只要它是在奇数位,并且与后一个数不等,那就是我们要返回的数了。

但是这个方法不符合题目提出的时间、空间的要求。

所以我们想到了异或运算符。

方法二: 利用异或。

那异或的运算规则是什么样的?

相同的数异或为0,任何数与0异或为任何数。

AC代码

/**
 * @param {number[]} nums
 * @return {number}
 */
var singleNumber = function(nums) {
    let ans = 0;

    for(let i = 0; i < nums.length; i++){
        ans ^= nums[i];
    }
    
    return ans;
};

 

总结

这一题的重点就是位运算符异或!如果想不到就没法解,但凡题目要求不要额外的空间,我们就得往位运算符上靠。

回复

我来回复
  • 暂无回复内容