4ms java solution


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

  • 1
    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.


  • 0
    X

    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,Object

    Could 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()]);
        }
    }
    

  • 0

  • 0
    X

    @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[]??


  • 0
    N

    @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.


  • 0
    X

    @ningzhao Thank you so much for your explanations!


  • 0
    E

    Hi ningzhao,

    I have a similar 3ms solution, I use array to store, then cut it to the length of the actual results, using:

    Arrays.copyOfRange();
    

    Here's my code:

    class Solution {
        public int[] intersect(int[] nums1, int[] nums2) {
            int p1 = 0;
            int p2 = 0;
            int length1 = nums1.length;
            int length2 = nums2.length;
            int[] result = new int[Math.min(length1,length2)];
            int counter = 0;
            Arrays.sort(nums1);
            Arrays.sort(nums2);
            while (p1 < length1 && p2 < length2){
                if(nums1[p1] == nums2[p2]){
                    result[counter] = nums1[p1];
                    p1++;
                    p2++;
                    counter++;
                }else if(nums1[p1] > nums2[p2]){
                    p2++;
                }else{
                    p1++;
                }
            }
            return Arrays.copyOfRange(result, 0, counter);
        }
    }
    

  • 0
    C

    Can anyone explain why this sort first solution has better run time than the hash map solution?
    To my understanding the sort first solution's run time should be O(NlogN + N) and the hashmap solution's runtime should be O(N) (N is the max of nums1, nums2 's length )
    THX

    Here is my 8ms hashmap solution

    class Solution {
        public int[] intersect(int[] nums1, int[] nums2) {
            Map<Integer, Integer> map = new HashMap();
            int[] ans = new int[Math.min(nums1.length, nums2.length)];
            int k = 0;
            for(int i= 0; i < nums1.length; i++) {
                if (!map.containsKey(nums1[i])) {
                    map.put(nums1[i], 0);
                }
                map.put(nums1[i], map.get(nums1[i])+1);
            }
            for(int i = 0; i < nums2.length; i++) {
                if (map.containsKey(nums2[i]) && map.get(nums2[i]) > 0) {
                    map.put(nums2[i], map.get(nums2[i]) - 1);
                    ans[k] = nums2[i];
                    k++;
                       }
            }
            return Arrays.copyOf(ans, k); 
           
        }
    }
    

Log in to reply
 

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