leetcode-136-Single Number

题目描述:

Given an 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?

要完成的函数:

int singleNumber(vector<int>& nums)

说明:

1、给定一组数,这组数中除了有一个元素只出现一次,其他元素都出现了两次,要求输出这个只出现一次的元素的值。

2、时间复杂度O(n),也就是只能从头到尾遍历一次;空间复杂度O(1),只能使用常数级的空间。

3、照这道题目的要求来看,既不能常规做法的定义一个数组,记录每个数出现了几次;也不能双重循环找到出现两次的数,然后把它们都删掉,接着继续遍历,直到最后只剩下出现一次的数。所以这道题目要求只能遍历一遍,那就只能从数学上寻找方法了。

4、这道题目笔者本人想了很长时间,都不知道采用什么数学方法好,直到在discuss中看到大神采用异或(XOR)的做法……以下举例说明为什么异或能够处理这道问题。

举例说明:

先说明一点,所有整数在计算机中都采用二进制的表示方法。以下举两个例子:

1、数组为1、1、2,在计算机中表示为0001,0001,0010,那么0001^0001=0000,接着0000^0010=0010。最后得到的结果是2,也就是只出现一次的这个数,2。

2、数组为1、2、1,在计算机中表示为0001,0010,0001,那么0001^0010=0011,接着0011^0001=0010。最后得到的结果是2,也就是只出现一次的这个数,2.

为什么会这样子?

因为异或是两个相同的数则异或结果为0,两个不同的数异或结果为1,并且异或满足交换律和结合律,所以我们可以得到这样的结论:A^B^C^B^D^C^A=D。

异或其实是“记录”了所有出现过的数,只要你第二遍出现,异或结果就会为0,直到一个只出现一次的数,那么异或结果最终为这个只出现一次的数的数值。

这个结论其实我思考了一会,才明白了过来。异或能够记录曾经出现过的数,然后一直在等待第二遍出现,来异或为0。如果一直没有第二遍出现,数组中全都是只出现一遍的数,那么最终结果会是很奇怪的。各位同学不妨试试。

异或就是我想要的那个数学方法。

代码:

int singleNumber(vector<int>& nums) 
{
  
  for(int i=1;i<nums.size();i++)
        nums[0]^=nums[i];
    return nums[0];
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏小樱的经验随笔

基数排序与桶排序,计数排序【详解】

桶排序简单入门篇^-^ 在我们生活的这个世界中到处都是被排序过的东东。站队的时候会按照身高排序,考试的名次需要按照分数排序,网上购物的时候会按照价格排序,电子邮...

3667
来自专栏CodingToDie

Python学习(十):有趣的字符串

第10 章 Python 字符串 学的到东西的事情是锻炼,学不到的是磨练 Table of Contents 字符串更新 转义字符 原始字符串 运算 连接 重复...

4197
来自专栏数说工作室

【SAS Says】基础篇:3. 描述数据

本节介绍如何利用SAS写一份数据报告,给出数据的基本信息。 从3.11开始的内容,是留给处女座的,主要说如何用proc tabulate和proc report...

34310
来自专栏JackieZheng

初探JavaScript(四)——作用域链和声明提前

前言:最近恰逢毕业季,千千万万的学生党开始步入社会,告别象牙塔似的学校生活。往往在人生的各个拐点的时候,情感丰富,感触颇深,各种对过去的美好的总结,对未来的展望...

2005
来自专栏追不上乌龟的兔子

[LeetCode Weekly Contest 88]848. 字母移位

早上参加了leetcode的周赛,好久没有比过赛,很多细节没有第一时间考虑到,AC了前两道题目,第三道题目超时,第四道没时间做了。在这里给大家展示一下题目和我的...

2324
来自专栏数据结构与算法

洛谷P1043 数字游戏

题目描述 丁丁最近沉迷于一个数字游戏之中。这个游戏看似简单,但丁丁在研究了许多天之后却发觉原来在简单的规则下想要赢得这个游戏并不那么容易。游戏是这样的,在你面前...

3455
来自专栏计算机视觉与深度学习基础

HDU2066

神坑的题目 思路就是枚举起点,迪杰斯特拉求最短路径,再枚举终点(如果起点终点一起枚举可能会超时,也能勉强扯上动态规划的思想吧),求最短路径。 如果剪枝可以加一个...

2327
来自专栏数据结构与算法

agc016C - +/- Rectangle(构造 智商题)

我的思路:直接按样例一的方法构造,若$h \times w$完全被$N \times M$包含显然无解

1131
来自专栏计算机视觉与深度学习基础

Leetcode 17 Letter Combinations of a Phone Number

Given a digit string, return all possible letter combinations that the number c...

18810
来自专栏java一日一条

使用Java 8函数式编程生成字母序列

在 Java 8 中使用函数式编程生成字母序列是一个很大的挑战。Lukas Eder 愉快地接受了这个挑战,他将告诉我们如何使用 Java 8 来生成ABC的序...

792

扫码关注云+社区

领取腾讯云代金券