leetcode

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 };