Can we do better than O(n^2) in Java?


  • 1
    Z

    I have the following code got TLE:

    public int removeDuplicates(int[] A) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
        if(A.length == 0) return A.length;
        int curInt = A[0];
        int len = A.length;
        for(int i = 1; i < len; i++){
            if(curInt == A[i]){
                for(int j = i; j < len-1; j++){
                    A[j]=A[j+1];
                }
                len--;
                i--;
            }
            else{
                curInt = A[i];
            }
        }
        return len;
    }
    

    It is very intuitive: traverse the array and keep track of the integer you are comparing to. If the ith element in the array equals the integer, remove it; otherwise, let the integer equal A[i];

    The problem is my removal for each duplicate takes O(n), so overall it is O(n^2). I did exactly the same thing in Remove Duplicated from Array II problem and got accepted. I do not understand why it is not acceptable here. Could someone explain? Thanks!


  • 23
    Z
    public static int removeDuplicates(int[] A) {
    	int count = 0;
    	int len = A.length;
    	for (int i = 0; i < len; i++) {
    		if (count == 0 || A[i] != A[count - 1]) {
    			A[count++] = A[i];
    		}
    	}
    	return count;
    }
    

    seems a little bit more concise. if there is a duplicate number A[i] = A[i - 1], just continue to the next element in A[], and if A[i] != A[i - 1], we can set the A[count] as A[i] and add 1 to count at the same time (count++).


  • 2
    D
    public int removeDuplicates(int[] A) {
            int distinct = 0;
            int lastNum = 0;
            if(A.length == 0){
                return 0;
            }else{
                lastNum = A[0];
                distinct = 1;
            }
            for(int i = 1; i < A.length;){
                if(A[i] == lastNum){
                    i++;
                }else{
                    A[distinct] = A[i];
                    distinct++;
                    lastNum = A[i];
                    i++;
                }
            }
            
            return distinct;
        }

  • 0
    Z

    Thanks, zihan. Just make it a slightly(really slightly) more concise: you can set both initial value of count and i to 1 (you never need to look at the first element) and get rid of the count==0 in the if condition.


  • 0
    Z

    thanks, zchen!


  • 0
    R

    excellent idea!


  • 0
    N

    but then you will be returning size 1 if the "edge case" of empty array [] appears as input.


  • 0
    R

    Core idea: store distinct numbers in A[0 : checked]

    public class Solution {
        public int removeDuplicates(int[] A) {
            		
    		if (null == A || A.length == 0) return 0;
    		
    		int checked = 0, toCheck = 1;
    		while(toCheck < A.length){
    			if (A[checked] == A[toCheck]) {
    				toCheck++;
    			} else {
    				A[++checked] = A[toCheck++];
    			}
    		}
    		
    		return (checked + 1);
        }
    }

  • 0
    R

    Not sure if I am wrong but I just use test case [1,4,4,4,5] and get [1, 4, 5, 4, 5] in the end of function, I think the question is asking give A= [1,1,2], return [1,2] along with the length.


  • 0
    1

    I have the same question


  • 0
    Z

    "remove the duplicates in place such that each element appear only once and return the new length.Do not allocate extra space for another array". we can not allocate extra memory, just in place which means we operate based on the original array. your test case is true, we get 14545 but we only consider the non-duplicate elements, and it's actually not a new array but only a sub-array with no duplicates


  • 0
    1

    Thanks for your detailed explanation and your solution is excellent,zihan.


Log in to reply
 

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