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

Question

我最近在一次采访中被问到这个问题：

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

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

有一个更好的方法吗 ？

谢谢。

Answer 1

好吧，您可以使用O(1). 由于它是一个排序数组，因此您只需将当前数字与下一个数字相减即可。如果结果是，0那么你有一个重复的数字。

Answer 2

检查数组中的每个元素（最后一个元素除外）与下一个元素，如果它们相等，则停止并退出：你找到了一个重复的元素。它之所以有效，是因为数组已排序，它不需要任何额外的空间，并且在最坏的情况下（没有重复元素）它将是 O(n)，因为必须遍历所有数组。

Answer 3

- 对数组进行排序

-找到相邻索引值之间的差异

- 如果差异为 0，则重复并记下索引

Answer 4

public static int searchrepeativeVal(int a[]){

    int left =0;
    int right= a.length;
    int mid;

    while (right-left>1){

        mid= (left+right)/2;

        if(a[mid]!=mid+1){
            if(a[mid]== mid){
                return mid;
            }else{
                right=mid;
            }
        }else{

            if(a[mid]==mid ){
                return mid;
            }else{
                left =mid;
            }
        }
    }

    return -1;
}