4ms java solution


  • 19
    N
            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;

  • 0
    E

    Same as yours.


  • 0
    S

    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;
        }
    }

  • 0
    N

    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.


  • 0
    H

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


  • 0
    S

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


  • 0
    H

    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,freq-1);
                    if(freq-1==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;
            }
        }
    

  • 0
    H

    @shawntsai I checked twice too. may be OJ! Yes to 2nd question.


Log in to reply
 

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