leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

2215.cpp (2347B)

0 // Solution 1: time O(n); space O(n) 1 class Solution { 2 public: 3 vector<vector<int>> findDifference(vector<int> &nums1, vector<int> &nums2) { 4 unordered_set<int> s1(nums1.begin(), nums1.end()); 5 unordered_set<int> s2(nums2.begin(), nums2.end()); 6 vector<vector<int>> res(2); 7 for (auto num : s1) 8 if (!s2.count(num)) res[0].push_back(num); 9 for (auto num : s2) 10 if (!s1.count(num)) res[1].push_back(num); 11 return res; 12 } 13 }; 14 15 // Solution 2: time O(nlogn); space O(1) 16 class Solution { 17 public: 18 vector<vector<int>> findDifference(vector<int> &nums1, vector<int> &nums2) { 19 vector<vector<int>> res(2); 20 21 int i = 0, j = 0; 22 sort(nums1.begin(), nums1.end()); 23 sort(nums2.begin(), nums2.end()); 24 while (i < nums1.size() && j < nums2.size()) { 25 while (i < nums1.size() - 1 && nums1[i] == nums1[i + 1]) 26 i++; 27 while (j < nums2.size() - 1 && nums2[j] == nums2[j + 1]) 28 j++; 29 30 if (i >= nums1.size() || j >= nums2.size()) 31 break; 32 else if (nums1[i] < nums2[j]) 33 res[0].push_back(nums1[i++]); 34 else if (nums1[i] > nums2[j]) 35 res[1].push_back(nums2[j++]); 36 else 37 i++, j++; 38 } 39 40 while (i < nums1.size()) { 41 res[0].push_back(nums1[i]); 42 while (++i < nums1.size() && nums1[i - 1] == nums1[i]) 43 ; 44 } 45 46 while (j < nums2.size()) { 47 res[1].push_back(nums2[j]); 48 while (++j < nums2.size() && nums2[j - 1] == nums2[j]) 49 ; 50 } 51 52 return res; 53 } 54 }; 55 56 // Solution 3: time O(1); space O(n) 57 class Solution { 58 public: 59 vector<vector<int>> findDifference(vector<int> &nums1, vector<int> &nums2) { 60 vector<vector<int>> res(2); 61 62 bitset<2002> bs1, bs2; 63 for (auto num : nums1) 64 bs1.set(num + 1000); 65 for (auto num : nums2) 66 bs2.set(num + 1000); 67 68 for (int i = 0; i < 2002; i++) { 69 if (bs1[i] && bs2[i]) 70 continue; 71 else if (bs1[i]) 72 res[0].push_back(i - 1000); 73 else if (bs2[i]) 74 res[1].push_back(i - 1000); 75 } 76 77 return res; 78 O 79 } 80 };