首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >最常见面试算法之只出现1次的数字

最常见面试算法之只出现1次的数字

作者头像
阿宝哥
发布2020-02-14 11:19:14
3550
发布2020-02-14 11:19:14
举报
文章被收录于专栏:全栈修仙之路全栈修仙之路

一、题目描述

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

说明:

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

示例 1:

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

示例 2:

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

二、题解

2.1 列表操作

算法分析

1、遍历数组中的每一个元素

2、如果当前元素是新出现的,则将它添加到列表中

3、如果当前元素已经存在列表中,则从列表中删除它

JavaScript Code:

function singleNumber(nums){
  let items = [];
  for(let num of nums) {
    let index = items.indexOf(num);
    if(index != -1) {
      items.splice(index, 1);
    } else {
      items.push(num);
    }
  }
  return items.pop();
}

上述的 JavaScript 实现虽然实现了功能,但需要一个额外的数组来存储 nums 数组中的元素,此外除了遍历原始的 nums 数组外,我们还需要遍历 items 数组,判断当前的元素是否已经存在列表中,这样导致该算法的时间复杂度为 O(n2) 。

2.2 哈希集(HashSet)

为了减少列表操作算法的时间复杂度,我们可以使用哈希集来避免每次查找元素是否存在需要的 O(n) 时间。

算法分析

1、遍历数组中的每个元素

2、判断哈希集中是否有当前的元素

3、如果不包含当前的元素,则将当前元素添加到集合中

4、循环结束后获取哈希集中的元素

JavaScript Code:

function singleNumber(nums){
  const set = new Set();
  for(let num of nums) {
    if(set.has(num)){
        set.delete(num);
    } else {
        set.add(num);
    }
  } 
  return [...set][0];
}

使用哈希集的方式,虽然减少列表操作算法的时间复杂度,但仍然需要开辟额外的空间来存储 nums 中的元素。下面我们来介绍另一种算法,即不使用额外空间来实现同样的功能。

2.3 按位异或

在介绍具体解法时,我们先来了解一下异或运算,其运算规则如下:

1 ⊕ 1 = 0
1 ⊕ 0 = 1
0 ⊕ 1 = 1
0 ⊕ 0 = 0

此外,异或运算有以下几个特点:

1、一个数与 0 进行异或运算等于它本身:a ⊕ 0 = a;

  0000 1111 //a=15
⊕ 0000 0000
------------
  0000 1111

2、一个数与它本身进行异或运算等于 0:a ⊕ a = 0;

  0000 1111 //a=15
⊕ 0000 1111 //a=15
------------
  0000 0000

3、异或运算满足加法交换律和结合律:a ⊕ b ⊕ a = (a ⊕ a) ⊕ b = 0 ⊕ b = b。

a ⊕ b ⊕ a
  0000 1111 //a=15
⊕ 0000 1000 //b=8
------------
  0000 0111 //a ⊕ b的结果
⊕ 0000 1111 //a=15
------------
  0000 1000 // a ⊕ b ⊕ a的结果

因此基于以上异或运算的特点,将所有数字按照顺序做异或运算,最后剩下的结果即为唯一的数字。

Java Code:

public int singleNumber(int[] nums) {
    int ans = 0;
    for(int num: nums) {
        ans ^= num;
    }
    return ans;
}

JavaScript Code:

function singleNumber(nums) {
    let ans = 0;
    for(const num of nums) {
        ans ^= num;
    }
    return ans;
}

三、参考资源


欢迎小伙伴们订阅前端全栈修仙之路,及时阅读 Angular、TypeScript、Node.js/Java和Spring技术栈最新文章。

本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2020/01/17,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 一、题目描述
  • 二、题解
    • 2.1 列表操作
      • 2.2 哈希集(HashSet)
        • 2.3 按位异或
        • 三、参考资源
        相关产品与服务
        对象存储
        对象存储(Cloud Object Storage,COS)是由腾讯云推出的无目录层次结构、无数据格式限制,可容纳海量数据且支持 HTTP/HTTPS 协议访问的分布式存储服务。腾讯云 COS 的存储桶空间无容量上限,无需分区管理,适用于 CDN 数据分发、数据万象处理或大数据计算与分析的数据湖等多种场景。
        领券
        问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档