arrays - 排序数组中的重复数字

Question

我最近在面试中被问到这个问题:

在排序数组中查找重复数字的最有效方法是什么？

我的答案是基于使用哈希表，其中键作为数组元素，数组中的重复次数作为值；迭代数组并更新哈希表。最后，可以检查哈希表中 count > 1 的元素；这些是重复的元素。

有更好的方法吗？

谢谢。

Answer 1

好吧，你可以用 O(1) 的空间来做到这一点。因为它是一个排序数组，所以你需要做的就是用下一个数字减去当前数字。如果结果是 0，那么您有一个重复的数字。