Contains Duplicate

Contains Duplicate

문제

nums 배열 안에서, 중복되는 숫자가 있으면 true를 없다면 false를 리턴해야 함!

문제의 핵심

• 첫 시도
  배열의 0번째 숫자를 기준으로 2중 for문을 돌려 nums의 모든 요소들과 비교하다 같은 값이 나오는 순간 true를 리턴하는 방식으로 처리하였음

var containsDuplicate = function(nums) {
    for(let i = 0; i < nums.length; i++){

        let firstnum = nums[i];

        for(let j = i+1; j < nums.length; j++){
            if(firstnum === nums[j]){
                return true
            }
        }
    }
    return false;
};

• 두 번째 시도
  sort()를 이용하여 오름차순으로 배열을 재정렬 한 뒤, 인접한 값들끼리만 비교하여 처리 속도를 개선하였음

var containsDuplicate = function(nums) {
    let sortNums = nums.sort((a,b) => a-b)

    for(let i = 0; i < sortNums.length; i++){
        if(sortNums[i] === sortNums[i+1]){
            return true;
        }
    }
    return false;
};

결과

Runtime이 약 32% 줄어들었다

• 1차 시도
  시간 복잡도 : O(n²)
  

• 2차 시도
  시간 복잡도 : O(n log n)