[LeetCode] 217. Contains Duplicate - 문제풀이

Description

배열내에 동일한 값을 가진 요소가 하나라도 있으면 true, 아니면 false를 반환하는 문제입니다.

Given an integer array nums, return true if any value appears at least twice in the array, and return false if every element is distinct.

Example 1:

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

Example 2:

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

Example 3:

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

Constraints:

• 1 <= nums.length <= 10^5
• -10^9 <= nums[i] <= 10^9

Solution 1. 정렬(Sort)

public boolean containsDuplicate(int[] nums) {
    // 1. sort
    int len = nums.length;
    Arrays.sort(nums);
    int temp = nums[0];
    for (int i = 1; i < len; i++) {
        if(nums[i]==temp){
            return true;
        }
        temp = nums[i];
    }
    return false;

    //2. Stream
    //return nums.length != IntStream.of(nums).distinct().count();
    //return nums.length != Arrays.stream(nums).distinct().count();
}

정렬(Sort) 후 탐색하는 방법 입니다. 정렬하면 동일한 요소는 인접한 인덱스에 위치하기 때문에 이전 요소와 값이 같을 경우 true를 반환하여 배열의 전체 요소를 탐색 후에도 같은값이 없으면 false를 반환해 줍니다.

• 시간 복잡도 : O(N) - 정렬에 들어가는 비용 제외
• 공간 복잡도 : O(N)

Solution 2. Stream API 이용

public boolean containsDuplicate(int[] nums) {
  
    //2. Stream
    return nums.length != IntStream.of(nums).distinct().count();
}

Stream API를 이용하여 함수형 프로그래밍처럼 구성한 코드 입니다. 중복을 제거하고 남은 요소의 length가 원본 배열의 length와 같으면 중복되는 요소가 없는 것이니 false, 다를 경우 중복된 요소가 있는 것이니 true를 반환해 줍니다. 

Reference

Contains Duplicate - LeetCode

Contains Duplicate - LeetCode