Created
June 13, 2014 14:41
-
-
Save flexelem/31a740ed7c593e1b3d4c to your computer and use it in GitHub Desktop.
Find common elements out of two sorted array
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import java.util.ArrayList; | |
public class FindCommonElementsInTwoArrays { | |
public ArrayList<Integer> findCommonElementsOfTwoArray(int[] array1, int[] array2) { | |
int[] larger = array1; | |
int[] smaller = array2; | |
if (array1.length < array2.length) { | |
larger = array2; | |
smaller = array1; | |
} | |
ArrayList<Integer> commonElementList = new ArrayList<>(); | |
for (int i = 0; i < smaller.length; i++) { | |
int x = bs(larger, 0, larger.length - 1, smaller[i]); | |
if (x == smaller[i]) { | |
commonElementList.add(x); | |
} | |
} | |
return commonElementList; | |
} | |
private int bs(int[] numbers, int left, int right, int key) { | |
if (left <= right) { | |
int mid = (left + right) / 2; | |
if (key == numbers[mid]) { | |
return key; | |
} | |
if (key > numbers[mid]) { | |
return bs(numbers, mid + 1, right, key); | |
} else { | |
return bs(numbers, 0, mid - 1, key); | |
} | |
} | |
return -1; | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import static org.junit.Assert.assertEquals; | |
import java.util.ArrayList; | |
import org.junit.Before; | |
import org.junit.Test; | |
public class FindCommonElementsInTwoArraysTest { | |
private FindCommonElementsInTwoArrays testClass; | |
@Before | |
public void setUp() { | |
testClass = new FindCommonElementsInTwoArrays(); | |
} | |
@Test | |
public void findCommonElemsEx1() { | |
int[] array1 = { 2, 5, 8, 17, 18, 34, 37, 55 }; | |
int[] array2 = { 3, 4, 5, 18, 31, 32, 55 }; | |
ArrayList<Integer> commonList = testClass.findCommonElementsOfTwoArray(array1, array2); | |
assertEquals(5, commonList.get(0).intValue()); | |
assertEquals(18, commonList.get(1).intValue()); | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
We can do this in O(m) as here we assumed both arrays are sorted. The above Algorithm will give O(mlogn) complexity.
Here m - the size of smaller array and n - the size of a bigger array.
Following code will give O(m) time complexity and O(1) space complexity.