不修改数组找出重复的数字算法精解
第一次写算法题解,算是新的尝试,前几个月的题解都在力扣里,好处是有很多测试用例,坏处是你写题解不太方便,我的很多解法和注释都在代码里面里。 正好在别的地方看到里这个题目但是在力扣里没找到,所以不仅要写解法,还需要写测试用例,挺有趣的。 原题来自
https://me.guanghechen.com/post/quiz/partition/find-duplicate-number/#footnote-2
PS: 这个博客效果是炫,太费 CPU了,我还是喜欢简洁些的
题目
给定一个长度为 N+1 的数列 A={a0,a1,a2⋯,aN}. 其中 1⩽ai⩽N,0⩽i⩽N,N⩾1.
在满足以下限制的前提下找出数组中任意一个重复的数字:不能修改输入的数组;只能使用 O(1) 的额外空间
这个题目的条件是精心挑选的,我理解为是为了算法而特意设定的约束条件。比方说
- 数组长度说 N + 1,而不是 N
- 数组里不包含 0
- 找到任意一个,而不是全部
所以简化下理解,数组里包含里一个从 1 ~ N 的自然序列,额外再加一个 1 ~ N 的数字。