java从复杂度<O（n）的排序数组中查找唯一元素

Question

一位采访者问我以下问题：

从十亿条记录的排序数组（如1,1,1,1,3,3,4,5,5,6,6,6,7,7,7,7,7,8,8……）中搜索唯一整数值（约1000）复杂度小于O（n）
注意：不要使用SET

我尝试实施的一个解决方案：

将该数组分成两组数组，然后迭代这两个子数组，如果元素不存在，则在hashmap中搜索，然后将其添加到hashmap中，否则将移动到下一次迭代

public static void main(String[] args) {
    int arr[] = {1,2,4,9,-3,5,6,3,6,12,5,6,2,-1,-3,6,87,9,2,3,5,7,9,1,0,1,3,5,7,6,3,8,6,3,21,45,6};
    int size1 =0, size2 = 0;
    HashMap<Integer, Integer> map = new HashMap<Integer,Integer>();
    System.out.println("length of Array:"+arr.length);

    if((arr.length)%2 == 0){
        size1 = size2 = arr.length/2;
    }else{
        size1 = (arr.length + 1)/2;
        size2 = (arr.length)/2;
    }

    for(int i=0;((size1-i-1)>= 0)||((size2+i)<(arr.length - 1));i++){
        if(map.containsKey(arr[size1 -i-1])== false){
            map.put(arr[size1 -i-1],arr[size1 -i-1]);
        }
        if(map.containsKey(arr[size2 + i]) == false){
            map.put(arr[size2 + i], arr[size2 + i]);
        }
    }

    System.out.println(map.keySet());

}

然后他问如果我们把数组分成n个集合会怎么样

那么复杂性是O（1）还是O（n/n）？可能吗

请建议是否有其他方法可以在不使用hashmap的情况下实现相同的功能

Answer 1

我会尝试一种基于二进制搜索的方法，从中间元素开始——如果它与其中一条边相同，那么可以使用数组已排序的事实，并消除这一半。如果它与边上的每一个不同，则将数组分成两半，然后递归地处理每一个数组

在最坏的情况下，这仍然是O（n），但平均而言，它可能比传递整个阵列更好（特别是在有许多重复的情况下）

示例-

1 1 1 1 1 2 2 2 2

可以分两步完成

Answer 2

你为什么不用集合代替地图呢。无论如何，Set不允许重复元素

public static void main(String[] args) {
    int arr[] = { 1, 2, 4, 9, -3, 5, 6, 3, 6, 12, 5, 6, 2, -1, -3, 6, 87,
            9, 2, 3, 5, 7, 9, 1, 0, 1, 3, 5, 7, 6, 3, 8, 6, 3, 21, 45, 6 };

    Set<Integer> aset = new HashSet<Integer>();

    System.out.println("length of Array:" + arr.length);

    for (int i : arr) {
        aset.add(i);
    }
    System.out.println(aset);
}