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[1024], set2 = new boolean[1024];
  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) {
  65.             if (set2.contains(num) && uniques.add(num))
  66.                 ans[++index] = num;
  67.         }
  68.         return Arrays.copyOfRange(ans, 0, index + 1);
  69.     }
  70. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top