题目描述:一堆机器的存储内容都有两个备份,其中有一个缺失了备份,求查找出这个缺失的备份机器,如果有两个丢失了怎么找?(假定两个不是同一个备份的两个)
解法:跟传统的题的解法一样,由浅入深的解题思路,此处提供四种方法。
1.正常途径:找出那个只出现一次的机器,进行线性搜索,需要o(n)的时间复杂度,将每台机器的出现次数进行记录需要o(n)的空间复杂度
2.优化空间:线性搜索,但是只用一个存储空间对搜索结果进行存储,所以空间复杂度o(1)
3.利用题中提到的两个备份:对所有ID进行异或求和,得到的结果为只有一个备份的机器,时间复杂度o(1),空间复杂度稍高些,o(n)。对于问题二,将a,b两台机器分成两拨,每拨用方法1,得出最终结果。
4.构造等式a+b,a*b求a,b:如果只有一台机器缺失,用全部机器ID和减去当前机器的ID和,为缺失机器的ID值。两台缺失则,同理求ID和,同理求缺失机器ID积,用数学方法求解a,b。
推广问题中的
1)三台机器缺失,同样的三种方法:简单搜索,优化空间,构造等式,不过这个时候构造等式就有点费劲
2)13张扑克中抽取一张,怎么样确定抽取的是那张,方法同样:简单搜索,无优化空间,构造等式---简单求差就可
总结:解法的基本套路:
1.简单的时间复杂度,空间复杂度最高的普通程序写法
2.优化时间或空间,不过是时间空间的互相转换此类
3.利用题中条件,用计算机方式解决,如异或,求与,求差等等,或者正则表达。
4.利用数学方法解题:解二次方程,多项式求积等!