求star

开源不易,喜欢请点个star吧

Ocean Han
391 字
2 分钟
Leetcode->只重复一次的数字
2022-06-12

题目#

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

说明:

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

示例 1:

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

示例 2:

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

解题方法:tada:#

①位运算:#

TIP

利用异或运算的性质:

  • 任何数和0异或等于它本身
    • 0 ^ n = n
  • 相同的数异或为0:
    • n ^ n = 0
  • 交换律
    • a ^ b ^ c = a ^ c ^ b

JS:#

/**
 * @param {number[]} nums
 * @return {number}
 */
var singleNumber = function(nums) {
    return nums.reduce((sum,item) => {
        sum ^= item
        return sum
    })
};

C:#

int singleNumber(int* nums, int numsSize){
    int a = 0;
    for (int i = 0; i < numsSize; i++)
    {
        a = a ^ nums[i];
    }
    return a;

}

②使用Set类#

​ 不过由于ES6中的Set类的add方法的返回值是当前set结构,而不是添加成功与否,所以用preSize保存添加之前的大小,用来判断是否添加成功,如果添加失败,则说明这个数是重复的,就把这个数从set里删除,最后剩下的就是只出现一次的数字

​ 另外需要注意一点的是,此题目有一个前提”其他数均出现两次”,如果没有这个前提的话,这样判断会有问题

/**
 * @param {number[]} nums
 * @return {number}
 */
var singleNumber = function(nums) {
   const s = new Set()
   for(num of nums){
       let preSize = s.size
       s.add(num)
       if(s.size == preSize){
           s.delete(num)
       }
   }
   return Array.from(s)[0]
};
Leetcode->只重复一次的数字
https://blog.oceanh.top/posts/algorithm/只重复一次的数字/
作者
Ocean Han
发布于
2022-06-12
许可协议
CC BY-NC-SA 4.0
最后修改时间
2024-08-10 10:08:49