前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >【leetcode系列】136. 只出现一次的数字

【leetcode系列】136. 只出现一次的数字

作者头像
lucifer210
发布2019-08-16 11:32:43
3670
发布2019-08-16 11:32:43
举报
文章被收录于专栏:脑洞前端

题目地址

https://leetcode.com/problems/single-number/description/

题目描述

代码语言:javascript
复制
给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。

说明:

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

示例 1:

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

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

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/single-number
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

思路

根据题目描述,由于加上了时间复杂度必须是 O(n),并且空间复杂度为 O(1)的条件,因此不能用排序方法,也不能使用 map 数据结构。

我们可以利用二进制异或的性质来完成,将所有数字异或即得到唯一出现的数字。

关键点

  1. 异或的性质 两个数字异或的结果 a^b是将 a 和 b 的二进制每一位进行运算,得出的数字。运算的逻辑是 如果同一位的数字相同则为 0,不同则为 1
  2. 异或的规律
  • 任何数和本身异或则为 0
  • 任何数和 0 异或是 本身
  1. 很多人只是记得异或的性质和规律,但是缺乏对其本质的理解,导致很难想到这种解法(我本人也没想到)
  2. bit 运算

代码

代码语言:javascript
复制
/*
 * @lc app=leetcode id=136 lang=javascript
 *
 * [136] Single Number
 *
 * https://leetcode.com/problems/single-number/description/
 *
 * algorithms
 * Easy (59.13%)
 * Total Accepted:    429.3K
 * Total Submissions: 724.1K
 * Testcase Example:  '[2,2,1]'
 *
 * Given a non-empty array of integers, every element appears twice except for
 * one. Find that single one.
 *
 * Note:
 *
 * Your algorithm should have a linear runtime complexity. Could you implement
 * it without using extra memory?
 *
 * Example 1:
 *
 *
 * Input: [2,2,1]
 * Output: 1
 *
 *
 * Example 2:
 *
 *
 * Input: [4,1,2,1,2]
 * Output: 4
 *
 *
 */
/**
 * @param {number[]} nums
 * @return {number}
 */
var singleNumber = function(nums) {
  let ret = 0;
  for (let index = 0; index < nums.length; index++) {
    const element = nums[index];
    ret = ret ^ element;
  }
  return ret;
};

延伸

有一个 n 个元素的数组,除了两个数只出现一次外,其余元素都出现两次,让你找出这两个只出现一次的数分别是几,要求时间复杂度为 O(n) 且再开辟的内存空间固定(与 n 无关)。

和上面一样,只是这次不是一个数字,而是两个数字。还是按照上面的思路,我们进行一次全员异或操作, 得到的结果就是那两个只出现一次的不同的数字的异或结果。

我们刚才讲了异或的规律中有一个 任何数和本身异或则为0, 因此我们的思路是能不能将这两个不同的数字分成两组 A 和 B。分组需要满足两个条件.

  1. 两个独特的的数字分成不同组
  2. 相同的数字分成相同组

这样每一组的数据进行异或即可得到那两个数字。

问题的关键点是我们怎么进行分组呢?

由于异或的性质是,同一位相同则为 0,不同则为 1. 我们将所有数字异或的结果一定不是 0,也就是说至少有一位是 1.

我们随便取一个, 分组的依据就来了, 就是你取的那一位是 0 分成 1 组,那一位是 1 的分成一组。这样肯定能保证 2.相同的数字分成相同组, 不同的数字会被分成不同组么。很明显当然可以, 因此我们选择是 1,也就是 说 两个独特的的数字在那一位一定是不同的,因此两个独特元素一定会被分成不同组。

Done!

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2019-07-31,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 脑洞前端 微信公众号,前往查看

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

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

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 题目地址
  • 题目描述
  • 思路
  • 关键点
  • 代码
  • 延伸
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档