发现从有序阵列的复杂性和其中独特的元素;上） [英] find unique elements from sorted array with complexity < O(n)

问题描述

这是interveiewer问我以下的问题：

An interveiewer asked me below question:

从十亿记录排序的数组搜索出独特的整数值（约1000张）（如1,1,1,1,3,3,3,4,5,5,6,6,6,6， 6,7,7,7,7,7,7,8,8,8,8 ...........）与复杂度小于O（N）。
注意：不要使用SET

Search out unique integer values(approx. 1000) from a sorted array of billion records(like 1,1,1,1,3,3,3,4,5,5,6,6,6,6,6,7,7,7,7,7,7,8,8,8,8...........) with complexity less than O(n).
NOTE: NOt to use SET.

这是我想一个解决方案来实现：

One solution that i tried to implement:

鸿沟阵列分成两个组数组，然后循环两种子阵列和HashMap的搜索，如果元素亘古不变的退出，然后将其添加到HashMap中以其他方式移动到下一个迭代。

Divide that array into two set of arrays,then iterate both subarrays and search in hashmap if element doesnot exit,then add it into hashmap otherwise move to next iteration.

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套？

And its working as expected, then he asked what if we divide the array into n sets?

那么复杂度是O（1）或O（N / N）？这可能吗？

then the complexity would be O(1) or O(n/n)? Is it possible?

请建议如果有另一种方式，而无需使用HashMap来实现相同的？

Please suggest if there is another way to implement the same without using hashmap?

推荐答案

你为什么不使用一组，而不是地图。不管怎么说，设置不允许重复的元素。

why don't you use a Set instead of Map. Anyways, Set does not allow duplicate elements.

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);
}

这篇关于发现从有序阵列的复杂性和其中独特的元素;上）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！