读书笔记-编程之美-1.5快速找出故障机器

时间:2021-06-05 12:41:05

题目描述:一堆机器的存储内容都有两个备份,其中有一个缺失了备份,求查找出这个缺失的备份机器,如果有两个丢失了怎么找?(假定两个不是同一个备份的两个)

解法:跟传统的题的解法一样,由浅入深的解题思路,此处提供四种方法。

 

1.正常途径:找出那个只出现一次的机器,进行线性搜索,需要o(n)的时间复杂度,将每台机器的出现次数进行记录需要o(n)的空间复杂度

2.优化空间:线性搜索,但是只用一个存储空间对搜索结果进行存储,所以空间复杂度o(1)

3.利用题中提到的两个备份:对所有ID进行异或求和,得到的结果为只有一个备份的机器,时间复杂度o(1),空间复杂度稍高些,o(n)。对于问题二,将a,b两台机器分成两拨,每拨用方法1,得出最终结果。

4.构造等式a+b,a*ba,b:如果只有一台机器缺失,用全部机器ID和减去当前机器的ID和,为缺失机器的ID值。两台缺失则,同理求ID和,同理求缺失机器ID积,用数学方法求解a,b

 

 

推广问题中的

1)三台机器缺失,同样的三种方法:简单搜索,优化空间,构造等式,不过这个时候构造等式就有点费劲

213张扑克中抽取一张,怎么样确定抽取的是那张,方法同样:简单搜索,无优化空间,构造等式---简单求差就可

 

总结:解法的基本套路:

1.简单的时间复杂度,空间复杂度最高的普通程序写法

2.优化时间或空间,不过是时间空间的互相转换此类

3.利用题中条件,用计算机方式解决,如异或,求与,求差等等,或者正则表达。

4.利用数学方法解题:解二次方程,多项式求积等!