找出数组中的重复数字
面试题简述
给你一个长度为 n 的数组，每个元素的值都在 1 到 n-1 之间，至少有一个数字重复。要求空间复杂度 O(1) ，返回重复的数字以及它出现的次数，你怎么做？
面试官想听的
是否知道O(1)解决找重复数字的解法。
面试回答举例
这个题我会先从暴力和哈希思路讲起，再优化。
暴力是O(n²)，哈希是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、能把抽象问题转换为链表结构。
#面试##八股##大厂##校招#2025智力题复盘 文章被收录于专栏
带你复盘2025大厂智力题面试，拆解面试官到底想听啥
当奴隶主还有脸出来说话