c++ leetcode array find duplicate by O(N)
배열 { 1,2,3,3,5,} 에서 중복을 찾는 것은 쉽다. 그렇지만 O(N)으로 중복을 찾으려면? 코드 >> 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 #include #include #include #include // Find Duplicates by O(N) int FindDuplicates(std::vector& nums) { int k; for (int i = 0; i = 0) nums[k-1] = -nums[k-1]; else return nums[i]; } return -1; } int main() { std::vector nums = { 1,2,3,3,5,}; int ans =..
c++ leetcode 배열 Shorted Unsorted Continuous Subarray
이 문제는 만약 [2,6,4,8,10,9,15,22,3]과 같은 벡터가 있다면 정렬이 되기 위해 고쳐야 할 원소의 갯수를 구하는 문제이다. 정렬이 된다면 [2,3,4,6,8,9,10,15,22]일 것이다. 따라서 고쳐야 할 배열의 원소들은 [6,4,8,10,9,15,22,3]이고 그렇다면 이 원소의 갯수는 8이다. O(nLogN)의 복잡도로 푸는 것은 쉽다. 오른쪽 배열은 퀵 소트로 정렬하였다. [2,6,4,8,10,9,15,22,3] = [2,3,4,6,8,9,10,15,22] 다른 부분의 처음과 끝의 인덱스만 구하면 되기 때문이다. 하지만 O(N)으로 푸는 것은 꽤나 까다롭다. O(nLogn) case와 O(N)의 케이스를 적어 놓겠다. 코드 >> 1 2 3 4 5 6 7 8 9 10 11 12 13..
c++ leet code medium merge_interval 구현
Merge interval은 {2,5}, {8,15}, {1,3}, {10,13}, {11,17} 과 같은 interval을 겹치는 구간은 병합하고, 분리된 부분은 분리하는 방법이다. 코드 >> 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 #include #include #include #include // merge_intervals std::vector merge_intervals(std::vector& intervals) { std::sort(in..