赞
踩
1.题目:不能修改数组找出重复的数字。在一个长度为n+1的数组里所有的数字都在1-n的范围内,所以数组中至少有一个数字是重复的。请在数组中找出任意一个重复的数字,但不能修改输入的数组。例如,如果输入长度为8的数组{2,3,5,4,3,2,6,7},那么对应的输出应该是重复的数字2或者3。
分析:时间优先,我们可以创建另外一个辅助数组,然后复制数组按照数组中重复的数字的方法,很容易达到我们的要求,但是这要牺牲O(N)的时间复杂度。
空间优先:我们可以参照二分查找的思想进行查找,分为两部分,分别统计两部分的个数,个数多的一部分肯定含有重复数字,依次进行下去。这样的时间复杂度为O(nlogn)
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。