找出所缺的整数
14 January 2013
(源自算法导论(第二版)思考题4-2)
数组A[1..n]
包含0到n中的n个,给定辅助数组B[0..n]
1. 找出所缺的数字,要求耗时O(n)
2. 假设A中的元素使用二进制表示,唯一可用的操作是读取A[i]的第j位。设计算法找出所缺数字,仍然耗时O(n)
思路
1. 将B元素全部置n,然后把A中元素按位置放入B中,确实的数就是第一个n的位置序数
2. 利用一个特性,奇数和偶数的二进制的末位不同。设置B[i]=1-i%2
,然后把A中元素按位置放入B中。扫描B中元素,则缺失的那一个元素B[k]=1-k%2
blog comments powered by Disqus