当前位置:   article > 正文

时间优先和空间优先_算法时间优先级 空间优先级

算法时间优先级 空间优先级

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

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/小丑西瓜9/article/detail/508136
推荐阅读
相关标签
  

闽ICP备14008679号