중복 번호 찾기

난이도 중급
자주 묻는 질문 아마존 Apple 블룸버그 게시물에서 구글 Microsoft
배열 이진 검색 두 포인터조회수 56

주어진 정렬 (n + 1) 요소를 포함하는 nums 및 모든 요소는 1에서 n 사이입니다. 중복 요소가 하나만있는 경우 중복 번호를 찾습니다.

입력:
숫자 = {1, 3, 4, 2, 2}
출력:
2

입력:
숫자 = {3, 1, 3, 4, 2}
출력:
3

중복 번호 찾기에 대한 순진한 접근 방식

방법 1 (Brute Force)

인덱스 0에서 배열을 탐색하고 모든 요소에 대해 앞의 배열 요소에서 반복되는지 확인합니다.
반복되면 중복 요소이고 그렇지 않으면 다음 요소에 대해 계속합니다.
시간 복잡성 = 의 위에2)

JAVA 코드

public class FindTheDuplicateElement {
    private static int findDuplicate(int nums[]) {
        int n = nums.length;
        
        for (int i = 0; i < n; i++) {
            // For every element check if it is repeated in the elements ahead of it
            for (int j = i + 1; j < n; j++) {
                // If repeated, this is the duplicate element
                if (nums[j] == nums[i])
                    return nums[i];
            }
        }
        // No duplicate found
        return -1;
    }

    public static void main(String[] args) {
        // Example 1
        int nums[] = new int[]{1, 3, 4, 2, 2};
        System.out.println(findDuplicate(nums));

        // Example 2
        nums = new int[]{3, 1, 3, 4, 2};
        System.out.println(findDuplicate(nums));
    }
}

C ++ 코드

#include <bits/stdc++.h>
using namespace std;

int findDuplicate(int *nums, int n) {
    for (int i = 0; i < n; i++) {
        // For every element check if it is repeated in the elements ahead of it
        for (int j = i + 1; j < n; j++) {
            // If repeated, this is the duplicate element
            if (nums[i] == nums[j])
                return nums[i];
        }
    }
    // Duplicate not found
    return -1;
}

int main() {
    // Example 1
    int nums[] = {1, 3, 4, 2, 2};
    int n = sizeof(nums) / sizeof(nums[0]);
    cout<<findDuplicate(nums, n)<<endl;
    
    // Example 2
    int nums2[] = {3, 1, 3, 4, 2};
    n = sizeof(nums2) / sizeof(nums2[0]);
    cout<<findDuplicate(nums2, n);
    
    return 0;
}
2
3

방법 2 (정렬)

배열을 오름차순으로 정렬하면 중복 요소가 서로 인접 해 있습니다.
정렬 된 배열을 탐색하고 중복 요소를 반환합니다.
시간 복잡성 = O (n 로그 (n))

JAVA 코드

import java. util. Arrays;
public class FindTheDuplicateElement {
    private static int findDuplicate(int[] nums) {
        int n = nums.length;
        // Sort the array
        Arrays.sort(nums);
        // Check the adjacent elements
        for (int i = 0; i < n - 1; i++) {
            // If adjacent elements are equal, this is the duplicate element
            if (nums[i] == nums[i + 1])
                return nums[i];
        }
        // No duplicate found
        return -1;
    }
    
    public static void main(String[] args) {
        // Example 1
        int nums[] = new int[]{1, 3, 4, 2, 2};
        System.out.println(findDuplicate(nums));

        // Example 2
        nums = new int[]{3, 1, 3, 4, 2};
        System.out.println(findDuplicate(nums));
    }
}

C ++ 코드

#include <bits/stdc++.h>
using namespace std;

int findDuplicate(int *nums, int n) {
    // Sort the array
    sort(nums, nums + n);
    // Check the adjacent elements
    for (int i = 0; i < n - 1; i++) {
        // If adjacent elements are equal, this is the duplicate element
        if (nums[i] == nums[i + 1])
            return nums[i];
    }
    // Duplicate not found
    return -1;
}

int main() {
    // Example 1
    int nums[] = {1, 3, 4, 2, 2};
    int n = sizeof(nums) / sizeof(nums[0]);
    cout<<findDuplicate(nums, n)<<endl;
    
    // Example 2
    int nums2[] = {3, 1, 3, 4, 2};
    n = sizeof(nums2) / sizeof(nums2[0]);
    cout<<findDuplicate(nums2, n);
    
    return 0;
}
2
3

중복 번호 찾기를위한 최적의 방법

방법 1 (해싱)

HashSet을 만들고 nums 배열의 모든 요소에 대해 현재 요소가 HashSet에 있으면 중복이고 그렇지 않으면 요소를 HashSet에 삽입합니다.
시간 복잡성 = O (N)
공간 복잡성 = O (N)

중복 번호 찾기를위한 JAVA 코드

import java.util.*;
public class FindTheDuplicateElement {
    private static int findDuplicate(int[] nums) {
        int n = nums.length;
        // Create a HashSet
        HashSet<Integer> set = new HashSet<>();
        for (int i = 0; i < n; i++) {
            // If the HashSet contains the element, then this is the duplicate
            if (set.contains(nums[i]))
                return nums[i];
            // Else add the element to the set
            set.add(nums[i]);
        }
        // No duplicate found
        return -1;
    }
    
    public static void main(String[] args) {
        // Example 1
        int nums[] = new int[]{1, 3, 4, 1, 2, 5};
        System.out.println(findDuplicate(nums));

        // Example 2
        nums = new int[]{3, 1, 4, 2, 5, 5};
        System.out.println(findDuplicate(nums));
    }
}

중복 번호 찾기를위한 C ++ 코드

#include <bits/stdc++.h>
using namespace std;

int findDuplicate(int *nums, int n) {
    // Create a HashSet
    unordered_set<int> set;
    for (int i = 0; i < n; i++) {
        // If the HashSet contains the element, then this is the duplicate
        if (set.find(nums[i]) != set.end())
            return nums[i];
        // Else add the element to the set
        set.insert(nums[i]);
    }
    // Duplicate not found
    return -1;
}

int main() {
    // Example 1
    int nums[] = {1, 3, 4, 1, 2, 5};
    int n = sizeof(nums) / sizeof(nums[0]);
    cout<<findDuplicate(nums, n)<<endl;
    
    // Example 2
    int nums2[] = {3, 1, 5, 4, 2, 5};
    n = sizeof(nums2) / sizeof(nums2[0]);
    cout<<findDuplicate(nums2, n);
    
    return 0;
}
1
5

방법 2 (XOR)

XOR 속성 (X ^ X) = 0에 따라이 속성을 사용하여 위의 문제를 해결할 수 있습니다.

  1. 정수 X를 1에서 n까지 요소의 XOR로 초기화합니다. 여기서 nums 배열의 크기는 (n + 1)입니다.
  2. 다른 정수 Y를 0으로 초기화합니다.
  3. 배열을 가로 질러 Y를 (Y ^ nums [i])로 업데이트합니다. 즉, Y는 nums 배열의 모든 요소에 대한 XOR을 저장합니다.
  4. 중복 요소는 (X ^ Y)입니다.

시간 복잡성 = 의 위에), 두 번의 순회를 통해 하나는 X를 구축하고 하나는 Y를 위해
공간 복잡성 = O (1)

중복 번호 찾기를위한 JAVA 코드

public class FindTheDuplicateElement {
    private static int findDuplicate(int[] nums) {
        int n = nums.length;
        // Initialise X as XOR of elements from 1 to n
        // Size of nums is (n + 1), here represented as n
        int X = 0;
        for (int i = 1; i <= n - 1; i++)
            X = (X ^ i);

        // Initialise Y as 0 and update Y = Y ^ nums[i] at every iteration
        int Y = 0;
        for (int i = 0; i < n; i++) {
            Y = Y ^ nums[i];
        }
        
        // Duplicate element is (X ^ Y)
        return (X ^ Y);
    }

    public static void main(String[] args) {
        // Example 1
        int nums[] = new int[]{1, 3, 4, 2, 4};
        System.out.println(findDuplicate(nums));

        // Example 2
        nums = new int[]{3, 1, 3, 4, 2};
        System.out.println(findDuplicate(nums));
    }
}

중복 번호 찾기를위한 C ++ 코드

#include <bits/stdc++.h>
using namespace std;

int findDuplicate(int *nums, int n) {
    // Initialise X as XOR of elements from 1 to n
    // Size of nums is (n + 1), here represented as n
    int X = 0;
    for (int i = 1; i <= n - 1; i++)
        X = X ^ i;
    
    // Initialise Y as 0 and update Y = Y ^ nums[i] at every iteration
    int Y = 0;
    for (int i = 0; i < n; i++)
        Y = Y ^ nums[i];
    
    // Duplicate element is (X ^ Y)
    return (X ^ Y);
}

int main() {
    // Example 1
    int nums[] = {1, 3, 4, 2, 4};
    int n = sizeof(nums) / sizeof(nums[0]);
    cout<<findDuplicate(nums, n)<<endl;
    
    // Example 2
    int nums2[] = {3, 1, 3, 4, 2};
    n = sizeof(nums2) / sizeof(nums2[0]);
    cout<<findDuplicate(nums2, n);
    
    return 0;
}
4
3

방법 3 (사이클 감지)

위의 문제는 두 개의 포인터를 느리고 빠르게 사용하는 Linked List의 순환 찾기 알고리즘으로 해결할 수 있으며, 느린 포인터는 한 단계 씩 이동하고 두 단계 씩 빠르게 이동합니다.

예를 고려하십시오.
nums [] = {1, 3, 4, 2, 2}

중복 번호 찾기

  1. 두 포인터를 nums [0]만큼 느리고 빠르게 초기화합니다.
  2. slow = nums [slow] 및 fast = nums [nums [fast]]를 수행하는 반면 slow와 fast는 같지 않습니다.
  3. 2 단계 후에 slow를 nums [0]로 지정하고 느리고 빠른 포인터를 각각 한 단계 씩 이동합니다. 즉,
    slow = nums [slow]
    fast = nums [빠름]
    느리고 빠르다는 것은 같지 않습니다.
  4. 3 단계 후에는 느리고 빠름이 중복 요소를 가리 킵니다.

시간 복잡성 = O (N)
공간 복잡성 = O (1)

중복 번호 찾기를위한 JAVA 코드

public class FindTheDuplicateElement {
    private static int findDuplicate(int[] nums) {
        int n = nums.length;
        //Initialize two pointers slow and fast as nums[0].
        int slow = nums[0], fast = nums[0];
        // Do slow = nums[slow] and fast = nums[nums[fast]]
        // while slow and fast are not equal.
        do {
            slow = nums[slow];
            fast = nums[nums[fast]];
        } while (slow != fast);

        // assign slow as nums[0]
        slow = nums[0];
        // Move slow and fast by one step each while slow and fast are not equal
        while (slow != fast) {
            slow = nums[slow];
            fast = nums[fast];
        }

        // Both slow and fast points to the duplicate element
        return fast;
    }

    public static void main(String[] args) {
        // Example 1
        int nums[] = new int[]{1, 3, 4, 4, 2};
        System.out.println(findDuplicate(nums));

        // Example 2
        nums = new int[]{3, 1, 5, 4, 2, 5};
        System.out.println(findDuplicate(nums));
    }
}

중복 번호 찾기를위한 C ++ 코드

#include <bits/stdc++.h>
using namespace std;

int findDuplicate(int *nums, int n) {
    //Initialize two pointers slow and fast as nums[0].
    int slow = nums[0], fast = nums[0];
    // Do slow = nums[slow] and fast = nums[nums[fast]]
    // while slow and fast are not equal.
    do {
        slow = nums[slow];
        fast = nums[nums[fast]];
    } while (slow != fast);

    // assign slow as nums[0]    
    slow = nums[0];
    // Move slow and fast by one step each while slow and fast are not equal
    while (slow != fast) {
        slow = nums[slow];
        fast = nums[fast];
    }

    // Both slow and fast points to the duplicate element
    return fast;
}

int main() {
    // Example 1
    int nums[] = {1, 3, 4, 4, 2};
    int n = sizeof(nums) / sizeof(nums[0]);
    cout<<findDuplicate(nums, n)<<endl;
    
    // Example 2
    int nums2[] = {3, 1, 5, 4, 2, 5};
    n = sizeof(nums2) / sizeof(nums2[0]);
    cout<<findDuplicate(nums2, n);
    
    return 0;
}
4
5

참조e1   참조 2

Translate »