面试题——找出1000个连续数中出现的一个重复数
2023-01-04 12:01 投稿人：网络编辑
前些天去面试一家做ipad开发的公司，第一道题是找出1000个数（1-999）中一个重复的数。这1000个数是连续且乱序的。我的第一反应就是创建一个999的数组，然后根据数字找相应的数组下标，如果对应的为空则填充，如果有值则找到了重复的数。python版的解法如下：
# 创建测试数据，1000个数，随机排序，为了简单用了0-999
# 使用数组的方式查找
该方法是时间复杂度最低的，但是空间复杂最高。面试过后才想明白其实存储那1000个数的数组（这里是lst）本身就是存储空间，我无须再创建一个临时的1000数组。只要创建一个用于保存临时交换数字的空间就可以了。解题思路还和上面一样，按照数字与数组下标的对应关系，来填充到相应位置。只是每一次填充过程都是一个系列替换过程，比如[2,1,3,0]这样的数组，拿到第一个数字式2，则将[2]中的3保存到临时变量中，然后[2]=2，然后再将[3]中的0保存在临时变量中[3]=3，然后将[0]=0。这样一个交换过程就完成了。