(Easy - Arrays) Leetcode - 217. Contains Duplicate

 

Leetcode의 Easy 문제 중 Array와 관련된 문제다.

 

간단한 문제로 배열에서 value가 한 번이라도 반복되면 true를 반환, 반복되는 값이 하나도 없다면 false를 반환하면 된다.

 

내 풀이는 먼저 정렬을 사용해 배열을 정렬해 준 뒤 한 번이상 반복되는 값을 찾아주는 것이다.

bool containsDuplicate(vector<int>& nums) {
    std::sort(nums.begin(), nums.end()); // sort for comparison

    for (int i = 1; i < nums.size(); i++) {
        if (nums[i -1] == nums[i]) // compare current value with previous value
        	return true; 
    }
    return false;
 }

 

C++의 sort() 함수는 개선된 Quick Sort 알고리즘을 바탕으로 만들어져 O(n log n)의 시간복잡도를 보장한다.

이후 nums의 개수만큼 loop를 한 번 돌려주면서 이전의 값과 비교해 같으면 true를 반환해준다.

 

만약 정렬을 하지 않고 비교를 한다면 이중 Loop를 사용해야 하는데 시간 복잡도가 O(n^2)가 된다.