547. Intersection of Two Arrays

Leave a comment

July 2, 2016 by oneOokay

Solve it in three algorithms:

  1. hashmap; 2. two pointers; 3. binary search.

My very naive way: (BAD really BAD) (HashSet)

  1. two hashsets for array1 and array2 to hold distinct numbers.
  2. iterate one of the hashsets, find “intersection” numbers and put them into an ArrayList
  3. convert ArrayList to array.

Solution1: <HashSet> Improved

  1. two hashsets: one for array1 and one for result
  2. iterate array1, put distinct numbers into first hashset.
  3. iterate array2, find “intersection” numbers and put them into result hashset.
  4. convert hashset to array.

Key points here:

  1. HashMap Iteration: convert HashMap t0 Array:
    1. Iterator<Integer> iter = hashset.interator();
    2. iter.next().intValue();
    3. hashset.size()

CODE:

public int[] intersection(int[] nums1, int[] nums2) {
// Write your code here
if (nums1 == null || nums2 == null) {
return null;
}

HashSet<Integer> set = new HashSet<Integer>();
HashSet<Integer> resultHash = new HashSet<Integer>();

for (int i = 0; i < nums1.length; i ++) {
if (!set.contains(nums1[i])) {
set.add(nums1[i]);
}
}

for (int j = 0; j < nums2.length; j ++) {
if (set.contains(nums2[j]) && !resultHash.contains(nums2[j])) {
resultHash.add(nums2[j]);
}
}

Iterator<Integer> iter = resultHash.iterator();
int[] t =new int[resultHash.size()];
for (int i = 0; i < resultHash.size(); i ++) {
t[i] = iter.next().intValue();
}
return t;
}

Solution 2: two pointers

Key points:

  1. Sort an interger array: Arrays.sort(array);
  2. two pointers: while loop

public int[] intersection(int[] nums1, int[] nums2) {
// Write your code here
if (nums1 == null || nums2 == null) {
return null;
}

Arrays.sort(nums1);
Arrays.sort(nums2);
HashSet<Integer> set = new HashSet<Integer>();
int i = 0;
int j = 0;
while (i < nums1.length && j < nums2.length) {
if (nums1[i] == nums2[j]) {
if (!set.contains(nums1[i])) {
set.add(nums1[i]);
}
i ++;
j ++;
} else if (nums1[i] < nums2[j]) {
i ++;
} else if (nums1[i] > nums2[j]) {
j ++;
}
}

Iterator<Integer> iter = set.iterator();
int[] result = new int[set.size()];
for (int m = 0; m < set.size(); m ++) {
result[m] = iter.next().intValue();
}
return result;
}

Solution3: binary search

  1. Sort one array
  2. for each element in the other array, if it exist in the result hashset, then continue; it not, do binary search in the first array. if find it, add it to hashset. (THIS REDUCES binary search times!!!)
  3. convert hashset to array.

Key points:

  1. binary search templates.

CODE:

public int[] intersection(int[] nums1, int[] nums2) {
// Write your code here
if (nums1 == null || nums2 == null) {
return null;
}

Arrays.sort(nums1);
HashSet<Integer> set = new HashSet<Integer>();
for (int i = 0; i < nums2.length; i ++) {
if (set.contains(nums2[i])) {
continue;
}
if (binarySearch(nums1, nums2[i])) {
set.add(nums2[i]);
}
}

int[] result = new int[set.size()];
Iterator<Integer> iter = set.iterator();
for (int i = 0; i < set.size(); i ++) {
result[i] = iter.next().intValue();
}
return result;

}

public boolean binarySearch(int[] array, int target) {
if (array == null || array.length == 0) {
return false;
}
int start = 0;
int end = array.length – 1;
while (start + 1 < end) {
int mid = start + (end – start) / 2;
if (array[mid] == target) {
return true;
}

if (array[mid] > target) {
end = mid;
} else {
start = mid;
}
}
if(array[start] == target || array[end] == target) {
return true;
} else {
return false;
}
}

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: