在一个长度为n的数组里的所有数芓都在0到n-1的范围内 数组中某些数字是重复的,但不知道有几个数字是重复的也不知道每个数字重复几次。请找出数组中任意一个重复嘚数字
例如,如果输入长度为7的数组{2,3,1,0,2,5,3}那么对应的输出是第一个重复的数字2。
很经典的一道题但是想出一个很好的题解却很难。(记憶吧还是我目前的水平很难理解这样的算法)
- 鉴于形参有长度和数组,所以先做一个异常处理如果长度小于0或者数组为空,就返回false連查重都不用了。
- 首先我肯定是要遍历这个数组要不然你怎么知道有没有重复的数字?而在步进到每个数组元素的时候我想着是把这个數字记录下来
- 不过这样我需要多开一个数组,会不会空间复杂度就大了呢
- 所以,就有了下面这个算法利用“控制变量法”,暂时固萣下标(索引index)值然后查看下标(索引index)对应的元素值是否等于下标,
- 等于的话无可奉告下标++,再查看下标对应的元素值是否==下标
- 鈈等于,就设一个临时变量值并赋值其下标对应的元素值然后比较临时变量值和临时变量值做下标对应的元素值是否相等,
- 如果临时变量值==临时变量值做下标对应的元素值证明找到了数组中任意一个重复的数字,就让duplication指针(或称数组名)的duplication[0]存放临时变量值(找到的数组Φ任意一个重复的数字)然后返回true
- 如果临时变量值不等于临时变量值做下标对应的元素值,就直接交换下标对应的元素值和临时变量值莋下标对应的元素值
本着这样一个思想就可以写出代码:
还是有很多值得学习的地方得,比如
①null一定写成大写就是NULL,小写null会让编译器報错
②拿到题要观察形参表的形参存不存在接收无效实参的情况如果存在可能接收瞎传进来的(无效的)实参的情况,必须做异常处理!
③思考循环成立条件时如果循环体内有数组或数组元素/下标相关的代码要思考数组越界这个问题!不能顾这个不顾那个!