FilesExpand file tree

 master

/

IntersectionOfTwoArraysII350.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

115 lines (96 loc) · 3.31 KB

 master

/

IntersectionOfTwoArraysII350.java

Copy path

Top

File metadata and controls

• Code
• Blame

115 lines (96 loc) · 3.31 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

95

96

97

98

99

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

/**

* Given two arrays, write a function to compute their intersection.

*

* Example:

* Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2, 2].

*

* Note:

* Each element in the result should appear as many times as it shows in both arrays.

* The result can be in any order.

*

* Follow up:

* What if the given array is already sorted? How would you optimize your algorithm?

* What if nums1's size is small compared to nums2's size? Which algorithm is better?

* What if elements of nums2 are stored on disk, and the memory is limited such

* that you cannot load all elements into the memory at once?

*

*/

public class IntersectionOfTwoArraysII350 {

public int[] intersect(int[] nums1, int[] nums2) {

if (nums1.length == 0 || nums2.length == 0) return new int[0];

Map<Integer, Integer> m1 = new HashMap<>();

for (int i=0; i<nums1.length; i++) {

m1.put(nums1[i], m1.getOrDefault(nums1[i], 0)+1);

}

Map<Integer, Integer> m2 = new HashMap<>();

for (int i=0; i<nums2.length; i++) {

m2.put(nums2[i], m2.getOrDefault(nums2[i], 0)+1);

}

List<Integer> res = new ArrayList<>();

if (m1.size() > m2.size()) {

Map<Integer, Integer> temp = m1;

m1 = m2;

m2 = temp;

}

for (Map.Entry<Integer, Integer> e: m1.entrySet()) {

if (m2.containsKey(e.getKey())) {

int minVal = Math.min(e.getValue(), m2.get(e.getKey()));

while (minVal > 0) {

res.add(e.getKey());

minVal--;

}

}

}

int[] arr = new int[res.size()];

for (int i=0; i<res.size(); i++) arr[i] = res.get(i);

return arr;

}

// solution to 3rd follow-up

public int[] intersect2(int[] nums1, int[] nums2) {

int len = Math.min(nums1.length, nums2.length);

int[] arr = new int[len];

if (len == 0) return arr;

Map<Integer, Integer> m1 = new HashMap<>();

for (int i=0; i<nums1.length; i++) {

m1.put(nums1[i], m1.getOrDefault(nums1[i], 0)+1);

}

int size = 0;

for (int i=0; i<nums2.length; i++) {

if (m1.containsKey(nums2[i]) && m1.get(nums2[i]) > 0) {

m1.put(nums2[i], m1.get(nums2[i])-1);

arr[size] = nums2[i];

size++;

}

}

return Arrays.copyOfRange(arr, 0, size);

}

public int[] intersect3(int[] nums1, int[] nums2) {

int len = Math.min(nums1.length, nums2.length);

int[] arr = new int[len];

if (len == 0) return arr;

Arrays.sort(nums1);

Arrays.sort(nums2);

int i = 0;

int j = 0;

int size = 0;

while (i < nums1.length && j < nums2.length) {

int n1 = nums1[i];

int n2 = nums2[j];

if (n1 == n2) {

arr[size] = n1;

i++;

j++;

size++;

} else if (n1 < n2) {

do {

i++;

} while (i < nums1.length && nums1[i] == n1);

} else {

do {

j++;

} while (j < nums2.length && nums2[j] == n2);

}

}

return Arrays.copyOfRange(arr, 0, size);

}

}