最简单的方法,开个O(n)的空间,扫描一遍,吧出现的数的记录下来。再扫描一下找出丢失的数字。时间复杂度O(n)
如果不允许开空间:可以排序,然后遍历一遍找出未出现的数。采用基数排序O(d*n),当n<=100000是复杂度 O(7*n)解决O(n),不过破坏了原来的数组
不破坏原来数组的方法:如果小于n个数补0 补成n个数。
扫描数组,if(a[i]>0)a[a[i]]+=2*n;再扫描一遍 if(a[i]<=n) cout<<i<< " ";else a[i] -= 2*n;//恢复数组
O(2*n),不破坏原数组。
本文转自博客园知识天地的博客,原文链接:1,2,...n n个数m个丢失,找出丢失的数,如需转载请自行联系原博主。