• API
• FAQ
• Tools
• Archive
SHARE
TWEET # Untitled a guest Oct 19th, 2019 71 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. // https://leetcode.com/problems/intersection-of-two-arrays/
2. /* Runtime: 1 ms, faster than 99.85% of Java online submissions for Intersection of Two Arrays.
3.    Memory Usage: 37.2 MB, less than 89.19% of Java online submissions for Intersection of Two Arrays. */
4. private static class UsingArray implements Solution {
5.     public int[] intersection(int[] nums1, int[] nums2) {
6.         if (nums1.length < nums2.length) {
7.             int[] swap = nums1; nums1 = nums2; nums2 = swap;
8.         }
9.         int length = 0;
10.         boolean[] uniques = new boolean, set2 = new boolean;
11.         for (int num : nums2) set2[num] = true;
12.         for (int num : nums1) {
13.             if (set2[num] && !uniques[num]) {
14.                 uniques[num] = true;
15.                 ++length;
16.             }
17.         }
18.         int index = -1;
19.         int[] ans = new int[length];
20.         for (int i = 0; i < uniques.length; i++) {
21.             if (uniques[i]) {
22.                 ans[++index] = i;
23.             }
24.         }
25.         return ans;
26.     }
27. }
28.
29. /* Runtime: 1 ms, faster than 99.85% of Java online submissions for Intersection of Two Arrays.
30.    Memory Usage: 37.6 MB, less than 58.11% of Java online submissions for Intersection of Two Arrays. */
31. private static class UsingBitSet implements Solution {
32.     public int[] intersection(int[] nums1, int[] nums2) {
33.         if (nums1.length < nums2.length) {
34.             int[] swap = nums1; nums1 = nums2; nums2 = swap;
35.         }
36.         BitSet uniques = new BitSet(256), set2 = new BitSet(256);
37.         for (int num : nums2) set2.set(num);
38.
39.         int index = -1;
40.         int[] ans = new int[nums2.length];
41.         for (int num : nums1) {
42.             if (set2.get(num) && !uniques.get(num)) {
43.                 uniques.set(num);
44.                 ans[++index] = num;
45.             }
46.         }
47.         return Arrays.copyOfRange(ans, 0, index + 1);
48.     }
49. }
50.
51. /* Runtime: 2 ms, faster than 97.92% of Java online submissions for Intersection of Two Arrays.
52.    Memory Usage: 36.9 MB, less than 89.19% of Java online submissions for Intersection of Two Arrays. */
53. private static class UsingHashSet implements Solution {
54.     public int[] intersection(int[] nums1, int[] nums2) {
55.         if (nums1.length < nums2.length) {
56.             int[] swap = nums1; nums1 = nums2; nums2 = swap;
57.         }
58.         HashSet<Integer> set2 = new HashSet<>();
59.         for (int num : nums2) set2.add(num);
60.
61.         HashSet<Integer> uniques = new HashSet<>();
62.         int index = -1;
63.         int[] ans = new int[set2.size()];
64.         for (int num : nums1) {