Arrays.sort(nums1);
Arrays.sort(nums2);
int pnt1 = 0;
int pnt2 = 0;
ArrayList<Integer> myList = new ArrayList<Integer>();
while((pnt1 < nums1.length) &&(pnt2< nums2.length)){
if(nums1[pnt1]<nums2[pnt2]){
pnt1++;
}
else{
if(nums1[pnt1]>nums2[pnt2]){
pnt2++;
}
else{
myList.add(nums1[pnt1]);
pnt1++;
pnt2++;
}
}
}
int[] res = new int[myList.size()];
for(int i = 0; i<res.length; i++){
res[i] = (Integer)myList.get(i);
}
return res;
4ms java solution


similar to yours
public class Solution { public int[] intersect(int[] nums1, int[] nums2) { Arrays.sort(nums1); Arrays.sort(nums2); int p1 = 0; int p2 = 0; List <Integer> s = new ArrayList<>(); while(p1 < nums1.length && p2 < nums2.length){ if (nums1[p1] == nums2[p2]){ s.add(nums1[p1]); p1 ++; p2 ++; } else if (nums1[p1] < nums2[p2]) p1 ++; else p2 ++; } int [] r = new int[s.size()]; for (int i =0; i < s.size(); i++){ r[i] = s.get(i); } return r; } }

I did the same, except for the last line, which I use stream to convert the ArrayList to an int array:
list.stream().mapToInt(e>e).toArray();It takes 90ms to finish!
I was checking how come my code was so slow until I saw you have the same solution except for the last line.
I thought stream was an advanced feature added to Java 8, but now, I feel like it is like adding Python into Java.

@shawntsai I guess your solution is a bit slower than @ningzhao. Maybe because you have
if
andelse if
conditions which have to be checked instead of onlyif
condition in Ningzhao's solution?

@hihihahahoho I have submitted two solutions to compare. My solution is a little bit faster. But, I think our solutions are similar.

This is an example where O(NlogN) solution beats in time to my O(N) solution for available tests. Due to use of map lookups?
public class Solution { public int[] intersect(int[] nums1, int[] nums2) { HashMap<Integer,Integer> hm= new HashMap<>(); HashMap<Integer,Integer> result = new HashMap<>(); int resultLength=0,i=0; for(int n1: nums1){ if(hm.containsKey(n1)){ hm.put(n1,hm.get(n1)+1); } else hm.put(n1,1); } for(int n2: nums2){ if(hm.containsKey(n2)){ //this is a result candidate resultLength++; //for result array length if(!result.containsKey(n2)){result.put(n2,0);} // insert in result for first time result.put(n2,result.get(n2)+1); int freq = (int) hm.get(n2); //to manage the result candidate in hm hm.put(n2,freq1); if(freq1==0){hm.remove(n2);} } } int[] resultArray = new int[resultLength]; for (Map.Entry<Integer, Integer> entry : result.entrySet()) { int temp =0; while(temp<(int)entry.getValue()){ resultArray[i++] = entry.getKey(); temp++; } } return resultArray; } }


I did the same with you until I get the final list "myList". When transferring ArrayList into array, I use:
return list.toArray(new Integer[list.size()]);
But I got a compile error says:
error: incompatible types: inference variable T has incompatible upper bounds int,ObjectCould you please explain it? Thanks a lot!
And here's my code:
import java.util.Arrays; class Solution { public int[] intersect(int[] nums1, int[] nums2) { List<Integer> list = new ArrayList<>(); int len1 = nums1.length, len2 = nums2.length; int i=0, j=0; Arrays.sort(nums1); Arrays.sort(nums2); while(i<len1 && j<len2){ if(nums1[i] > nums2[j]){ j++; } else if(nums1[i] < nums2[j]){ i++; } else{ list.add(nums1[i++]); j++; } } return list.toArray(new Integer[list.size()]); } }

@XW_ZHAO https://stackoverflow.com/questions/13098960/convertarraylistofintegerobjectstoanintarray
hope this helps

@ningzhao
Thanks for your reply!According to your code, you defined an int[] 'res' first and give each element of 'res' an Integer value:
res[i] = (Integer)myList.get(i);
So, it is ok to give an int variable an Integer value, but cannot automatically transfer Integer[] to int[]??

@XW_ZHAO yep, the "(Integer)" is not necessary there. The reason (Integer) is still working there for my code, since it does not create a REAL new Integer Object. When res[i] = (Integer) list.get(i) happens, res[i] just get the primitive value of that Integer. If you have different idea, please let me know.
