DEV Community
·
在数组中寻找重复元素的聪明方法（无需额外空间！）
💡
原文英文，约300词，阅读约需1分钟。
📝
内容提要
LeetCode 442题通过索引标记法在O(n)时间内找到数组中的重复元素，且只需O(1)额外空间。该方法将每个数字视为索引，标记已访问的索引，遇到负数则表示重复，效率高且避免了排序。
🎯
关键要点
-
LeetCode 442题通过索引标记法在O(n)时间内找到数组中的重复元素。
-
该方法只需O(1)额外空间，无需排序或额外数据结构。
-
每个数字被视为索引，标记已访问的索引。
-
遇到负数表示该索引已被访问过，说明是重复元素。
-
示例数组为[4, 3, 2, 7, 8, 2, 3, 1]，通过标记索引找到重复元素。
-
该方法的时间复杂度为O(n)，空间复杂度为O(1)。
-
避免了排序操作，提升了效率。
-
这是一个高效的重复检测技巧，值得尝试。
❓
延伸问答
如何在数组中找到重复元素？
可以使用索引标记法，在O(n)时间内找到重复元素，且只需O(1)额外空间。
索引标记法的基本步骤是什么？
将每个数字视为索引，标记已访问的索引，遇到负数表示该索引已被访问过，说明是重复元素。
使用索引标记法的时间和空间复杂度是多少？
该方法的时间复杂度为O(n)，空间复杂度为O(1)。
为什么索引标记法比排序更高效？
索引标记法避免了排序操作，排序的时间复杂度为O(n log n)，而该方法只需O(n)。
能否给出一个使用索引标记法的示例？
例如，对于数组[4, 3, 2, 7, 8, 2, 3, 1]，通过标记索引可以找到重复元素2和3。
这个方法适用于哪些类型的问题？
适用于需要在数组中检测重复元素的问题，尤其是对空间复杂度有严格要求的场景。
➡️
