leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

2215.cpp (2347B)

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