不使用额外空间交换2个数据的源代码

  最近做求职笔试题,遇到比较有意思的题目,题目或多或少涉及到《剑指Offer》的思路和知识点,如果不是刷书两遍,估计不会做出来,分享一下互相学习!

************************************************************

1、不使用额外空间交换2个数据, 请写出任意3种方法,并阐明其优缺点。

  样例: int a = 2; int b = 3 ;   不再声明任何变量,使得 a = 3, b =2;

  解题思路: 部分参考自 http://www.cnblogs.com/cornucopia2015/p/4896791.html   不使用中间变量而交换两个数值变量的值,通常有三种做法: 1、加减法   a = a + b; b = a - b; a = a - b;   该方法可以交换整型和浮点型数值的变量,缺点是在处理浮点型的时候有可能会出现精度的损失。 2、乘除法   a = a * b; b = a / b; a = a / b;   该方法可以处理整型和浮点型变量,但在处理浮点型变量时也存在精度损失问题,而且乘除法比加减法要多一条约束:b必不为0,否则会报错。 3、异或法   a ^= b; // a=a^b   b ^= a; // b=b^(a^b)=b^a^b=b^b^a=0^a=a   a ^= b; // a=(a^b)^a=a^b^a=a^a^b=0^b=b   这里需要用到异或运算的一个性质:任何一个数字异或它自己都等于0。异或法可以完成对整型变量的交换,对于浮点型变量它无法完成交换。 4、栈法 (需要额外空间,不推荐)   push a; push b; pop a; pop b;   使用反向的出栈顺序来完成交换,它虽然没有显式的使用临时变量,但还是会用到额外的存贮空间,不太符合题意。

源代码:

  https://github.com/wylloong/TinyPrograms/blob/master/Coding%20Interviews/ExchangeWithoutTemp.cpp

************************************************************ 2、给定一个数组,数组中除了某个特定数字只出现1次,其余数字均出现2次。请编写函数,找出该数字。要求,空间复杂度O(n),时间复杂度O(n)。   1. 主程序需要包含对给定的2个测试文件的文件读取操作。   2. 请编写计时器类,并且对每个文件样例的输入和运算时间进行测量。

  解题思路: Google面试题,必须结合异或的性质,任何一个数字异或它自己都等于0,参考《剑指Offer》的面试题56:数组中数字出现的次数。

源代码:   https://github.com/wylloong/TinyPrograms/blob/master/Coding%20Interviews/FindNumsAppearOnce.cpp

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏菩提树下的杨过

python高级特性:切片/迭代/列表生成式/生成器

1633
来自专栏MasiMaro 的技术博文

C/C++中整数与浮点数在内存中的表示方式

在C/C++中数字类型主要有整数与浮点数两种类型,在32位机器中整型占4字节,浮点数分为float,double两种类型,其中float占4字节,而double...

803
来自专栏糊一笑

非比较排序算法总结与实现

之前一篇文章介绍了几种常用的比较排序算法,下面介绍的是几种非比较排序算法。 非比较排序算法内部引用的都是计数排序,当然你也可以将计数排序换为其他的比较排序算法。...

2888
来自专栏漫漫深度学习路

tensorflow错误总结

在写tensorflow代码的时候,经常会出现一些错误,在此记录一下,希望不要采同样的坑。 错误总结 bias = tf.get_variable("bias"...

1709
来自专栏偏前端工程师的驿站

基础野:细说无符号整数

Brief                                 本来只打算理解JS中0.1 + 0.2 == 0.30000000000000004...

1846
来自专栏机器学习算法全栈工程师

Sample K算法

0、题目来源    最近去国内某牛叉互联网公司面试,出了一道算法题,看似简单,但是真正的答案十分巧妙。故此回忆并将原题以及解题思路记录下来,供大家学习: 随机...

3318
来自专栏陈树义

BitMap 算法

什么是 BigMap 算法 所谓 BitMap 就是用一个 bit 位来标记某个元素对应的 value,而 key 即是这个元素。由于采用bit为单位来存储数据...

2846
来自专栏和蔼的张星的图像处理专栏

28. 搜索二维矩阵二分法

写出一个高效的算法来搜索 m × n矩阵中的值。 这个矩阵具有以下特性: 每行中的整数从左到右是排序的。 每行的第一个数大于上一行的最后一个整数。 样例...

482
来自专栏九彩拼盘的叨叨叨

学习纲要:ES6系列:箭头函数和对象方法简写

732
来自专栏青青天空树

c/C++二进制运算符

  1.  &  :  与操作.作用于两个二进制数,当然也可以对整型数据进行操作(当两边为整型数据会自动转化为二进制数).二进制与用来对位进行置零或者复位.如果...

532

扫描关注云+社区