面试题简述

给你一个长度为 n 的数组，每个元素的值都在 1 到 n-1 之间，至少有一个数字重复。要求空间复杂度为 O(1)，返回重复的数字以及它出现的次数，你怎么做？

面试官想听的

是否知道 O(1) 解决找重复数字的解法。

面试示例回答

这个题我会先从暴力和哈希思路讲起，再优化。

暴力是 O(n^2)，哈希是 O(n) 空间。但是由于题目要求 O(1) 的空间，因此要用指针思维。

详细内容可跳转该链接查看详情：http://xhslink.com/o/9YdrAnTRNgn

由浅入深分析

1、环检测思想：利用数组值作指针。

2、数学保证：由于1~n-1的映射必有重复，因此必有环。

3、时间复杂度：O(n)，空间复杂度：O(1)。

面试加分点

1、提出 Floyd 算法并能解释为什么可行。

2、强调空间 O(1) 是关键。

3、能把抽象问题转化为链表结构。