不使用额外空间交换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 条评论
登录 后参与评论

相关文章

来自专栏magicsoar

Effective Modern C++翻译(2)-条款1:明白模板类型推导

第一章 类型推导 C++98有一套单一的类型推导的规则:用来推导函数模板,C++11轻微的修改了这些规则并且增加了两个,一个用于auto,一个用于decltyp...

18510
来自专栏C语言及其他语言

[优秀题解]题目1277[Lucky Word]

题目描述 笨小猴的词汇量很小,所以每次做英语选择题的时候都很头疼。但是他找到了一种方法,经试验证明,用这种方法去选择选项的时候选对的几率非常大! 这...

2857
来自专栏小樱的经验随笔

hihoCoder 1039:字符消除(字符串处理)

#1039 : 字符消除 时间限制:1000ms 单点时限:1000ms 内存限制:256MB 描述 小Hi最近在玩一个字符消除游戏。给定一个只包含大写字母"A...

2948
来自专栏技术沉淀

Numpy 求100以内质数和

1315
来自专栏算法修养

PAT 1012 数字分类 (20)

给定一系列正整数,请按要求对数字进行分类,并输出以下5个数字: A1 = 能被5整除的数字中所有偶数的和; A2 = 将被5除后余1的数字按给出顺序进行交错...

2585
来自专栏SeanCheney的专栏

《利用Python进行数据分析·第2版》第4章 NumPy基础:数组和矢量计算4.1 NumPy的ndarray:一种多维数组对象4.2 通用函数:快速的元素级数组函数4.3 利用数组进行数据处理4.

NumPy(Numerical Python的简称)是Python数值计算最重要的基础包。大多数提供科学计算的包都是用NumPy的数组作为构建基础。 NumPy...

4368
来自专栏静默虚空的博客

排序一 冒泡排序

要点 冒泡排序是一种交换排序。 什么是交换排序呢? 交换排序:两两比较待排序的关键字,并交换不满足次序要求的那对数,直到整个表都满足次序要求为止。 算法思想 它...

2085
来自专栏Java帮帮-微信公众号-技术文章全总结

八大排序算法详解_面试+提升

八大排序算法详解_面试+提升 概述 排序有内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排...

3839
来自专栏猿人谷

C++ STL算法系列1---count函数

一.count函数 algorithm头文件定义了一个count的函数,其功能类似于find。这个函数使用一对迭代器和一个值做参数,返回这个值出现次数的统计结果...

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

P3709 大爷的字符串题(50分)

题目背景 在那遥远的西南有一所学校 /*被和谐部分*/ 然后去参加该省省选虐场 然后某蒟蒻不会做,所以也出了一个字符串题: 题目描述 给你一个字符串a,每次询问...

3367

扫码关注云+社区