# Three ways in Java: HashMap, sort one array, sort two arrays

• ## sort one array

sort the smaller array, then use a boolean array to mark whether this element in sorted array had been taken away. If we find an element equal to what we want, but has been taken away, then we find it in it's left or right surroundings.

``````public class Solution {
public int[] intersect(int[] nums1, int[] nums2) {
if(nums1.length<nums2.length){//make nums2 to be smaller
int[] tmp=nums2;
nums2=nums1;
nums1=tmp;
}
Arrays.sort(nums2);
boolean tag[]=new boolean[nums2.length];/mark every element whether be taken away
ArrayList<Integer> list=new ArrayList<>(nums2.length);
for(int i:nums1){
if(binarySearch(nums2,i,tag)){
list.add(i);
}
}
int[] res=new int[list.size()];
for(int i=0;i<list.size();i++){
res[i]=list.get(i);
}
return res;
}

private boolean binarySearch(int[] nums2,int i,boolean[] tag){
int left=0,right=nums2.length-1;
while(left<=right){
int mid=left+(right-left)/2;
if(nums2[mid]>i){
right=mid-1;
}else if(nums2[mid]<i){
left=mid+1;
}else{
if(tag[mid]==false){//haven't been taken away
tag[mid]=true;
return true;
}else{//find equal element in left or right
int p=mid+1,q=mid-1;
while(p<nums2.length&&nums2[p]==i&&tag[p]==true){
p++;
}
if(p==nums2.length){
return false;
}
if(nums2[p]==i){
tag[p]=true;
return true;
}

while(q>=0&&nums2[q]==i&&tag[q]==true){
q--;
}
if(q==-1){
return false;
}
if(nums2[q]==i){
tag[q]=true;//mark as taken
return true;
}
return false;
}
}
}
return false;
}
}

``````

## sort two arrays

``````public class Solution {
public int[] intersect(int[] nums1, int[] nums2) {
Arrays.sort(nums1);
Arrays.sort(nums2);
int i=0,j=0;
int maxLength=nums1.length<nums2.length?nums1.length:nums2.length;
ArrayList<Integer> list=new ArrayList<>(maxLength);
while(i<nums1.length&&j<nums2.length){
if(nums1[i]==nums2[j]){
list.add(nums1[i]);
i++;
j++;
}else if(nums1[i]<nums2[j]){
i++;
}else{
j++;
}
}
int[] res=new int[list.size()];
for(i=0;i<list.size();i++){
res[i]=list.get(i);
}
return res;
}
}
``````

## use HashMap to record frequency

``````public class Solution {
public int[] intersect(int[] nums1, int[] nums2) {
HashMap<Integer,Integer> map1=new HashMap<>(nums1.length);
HashMap<Integer,Integer> map2=new HashMap<>(nums2.length);
for(int i:nums1){
if(map1.containsKey(i)){
int freq=map1.get(i)+1;
map1.put(i,freq);
}else{
map1.put(i,1);
}
}
for(int i:nums2){
if(map2.containsKey(i)){
int freq=map2.get(i)+1;
map2.put(i,freq);
}else{
map2.put(i,1);
}
}
int l=(nums1.length<nums2.length?nums1.length:nums2.length);
ArrayList<Integer> list=new ArrayList(l);
for(int i: map1.keySet()){
if(map2.containsKey(i)){
int c1=map1.get(i);
int c2=map2.get(i);
int count=c1<c2?c1:c2;
while(count-->0){
list.add(i);
}
}
}
int[] res=new int[list.size()];
for(int i=0;i<list.size();i++){
res[i]=list.get(i);
}
return res;
}
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.