0에서 n-1까지의 그룹 무게 판정

2410 단어
수조에서 중복된 숫자를 구합니까?
public static void main(String[] args) {
        int[] data = {2, 3, 1, 0, 2, 5};
        Main main = new Main();
        main.isDuplicate(data);
    }
    public void isDuplicate(int[] arg){
        HashSet set  =  new HashSet<>();
        for (int a: arg) {
            if (set.contains(a)) {
                System.out.println(a);
            } else {
                set.add(a);
            }
        }
    }

먼저 우리가 생각한 것은hash이다.hash를 통해 한 숫자가 이전에 O(1)만 있으면 되는 시간의 복잡도를 판단한다.hashset의 밑바닥이 바로hashmap의 키,즉hash의 실현이라는 것을 알 수 있다.
그러나 데이터가 매우 어지러울 때hash는 공간의 복잡도를 매우 소모한다.예를 들어 수열 01963, 2, 15는 동시에hash의 충돌 시간이 발생할 수 있다.
숫자이기 때문에 그 수열에 있는 숫자는 0-n-1에만 나타나기 때문에 우리는 직접 주소 지정법을 사용해서hash의 충돌 시간을 피할 수 있고 공간의 복잡도를 줄일 수 있다.
 public static void main(String[] args) {
        int[] data = {2, 3, 1, 0, 2, 5};
        Main main = new Main();
        main.isDuplicate(data);
    }
    public void isDuplicate(int[] data){
        int len = data.length;
        int[] array = new int[len+1];
        for (int i = 0;i < len;i++){
            if(array[data[i]+1]==0) {
                array[data[i]+1] = data[i]+1;
            }else if(array[data[i]+1]==data[i]+1){
                System.out.println(data[i]);
            }
        }
    }

그러나 이렇게 공간의 복잡도도 O(n)이라고 해도 O(1)의 복잡도, 즉 로컬로 비교하려면 어떻게 해야 합니까?
빠른 배열의 교환 사상을 로컬에서 사용하여 데이터의 위치를 신속하게 포지셔닝할 수 있다. 또한 우리는nums[i]==i, 현재 위치의 데이터는 현재 위치의 좌표와 같아야 한다고 규정한다.이렇게 하면 O(1)의 공간 책임도를 사용하여 위치를 다시 정할 수 있다.
public static void main(String[] args) {
        int[] data = {2, 3, 1, 0, 2, 5};
        Main main = new Main();
        int[] duplication = new int[6] ;
        main.isDuplicate(data,6,duplication);
        System.out.println(duplication[0]);
    }
    public boolean isDuplicate(int[] data,int length,int[] duplication) {
        if (data == null || length <= 0)
            return false;
        for(int i = 0; i < length; i++){
            while(data[i]!=i){
                if(data[i]==data[data[i]]){
                    duplication[0] = data[i];
                    return  true;
                }
                swap(data,i,data[i]);
            }
        }
        return false;
    }

    private void swap(int[] data, int i, int j) {
        int a = data[i];
        data[i] = data[j];
        data[j] = a;
    }

좋은 웹페이지 즐겨찾기