[LeetCode] 287. Find the Duplicate Number - 문제풀이

Description

주어진 배열에서 중복되는값 하나를 찾아 반환하는 문제입니다.

Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive.

There is only one repeated number in nums, return this repeated number.

You must solve the problem without modifying the array nums and uses only constant extra space.

Example 1:

Input: nums = [1,3,4,2,2]
Output: 2

Example 2:

Input: nums = [3,1,3,4,2]
Output: 3

Constraints:

• 1 <= n <= 105
• nums.length == n + 1
• 1 <= nums[i] <= n
• All the integers in nums appear only once except for precisely one integer which appears two or more times.

Follow up:

• How can we prove that at least one duplicate number must exist in nums?
• Can you solve the problem in linear runtime complexity?

Solution 1. Set

public int findDuplicate(int[] nums) {
    int len = nums.length;
    Set<Integer> set = new HashSet<>();
    for (int i = 0; i < len; i++) {
        if(!set.add(nums[i])){
            return nums[i];
        }
    }
    return -1;
}

중복 자료를 저장하지 않는 Set를 사용해 중복되는 요소가 들어왔을 경우 해당 값을 반환해줍니다.

• 시간복잡도 : O(N)
• 공간복잡도 : O(N)

Solution 2. Binary Search

public int findDuplicate2(int[] nums) {
    if (nums.length == 0 || nums == null)
        return 0;
    int low = 1, high = nums.length - 1, mid;
    while (low < high) {
        mid = low + (high - low) / 2;
        int count = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] <= mid)
                count++;
        }
        if (count > mid)
            high = mid;
        else
            low = mid + 1;
    }
    return low;
}

이진검색을 통해 값을 찾아 나갑니다. 중간값(mid) 값보다 작거나 같은 총 갯수를 카운팅한 값이 mid보다 클 경우 중복은 start ~mid 사이에 있다는걸 알 수 있습니다. (중간크기보다 크기때문) 이런식으로 이진검색으로 분할해 나가면서 중복되는 값을 찾아나갑니다.

• 시간복잡도 : O(N Log N)
• 공간복잡도 : O(1)

Reference

Find the Duplicate Number - LeetCode