Is my code in linear time?


  • 0
    J
    public class Solution {
    public int singleNumber(int[] A) {
        int len = A.length;
        if(len==1){
            return A[0];
        }
        for(int i=0;i<len;i++){
            for(int j=len-1;j>i;j--){
                if(A[i]!=Integer.MAX_VALUE && A[i]==A[j]){
                    A[i] = Integer.MAX_VALUE;
                    A[j] = Integer.MAX_VALUE;
                    break;
                }
                else if(A[i]!=Integer.MAX_VALUE && j==i+1){
                    return A[i];
                }
            }
            if(i==len-1){
                return A[i];
            }
        }
        
        return 0;
    }
    

    }

    My code got TLE before I using len to store the value of A.length, but accepted after I did that. Is my code in linear time?

    Thanks


  • 0
    S

    I knew in cpp, length function always take O(N) to calculate, but I am not so sure about that in Java.


  • 0
    M

    Java takes O(1) time to return the length, as it is a simple accessor for a field.
    http://docs.oracle.com/javase/specs/jls/se7/html/jls-10.html#jls-10.7

    In slightly sadder news, what happens if the singleton is MAX_VALUE? It's apparently not a test, but that's a problem with sentinel values.


  • 0
    J

    You are right. But I cannot use null to tag the visited elements. Do you have any suggestions?


  • 0
    M

    I've checked again, apparently it does work. You just end up with the entire array being equal to the sentinel, and then the if(i==len-1) will return the sentinel value. You do end up destroying everything except the singleton and the sentinel in the array by the end of the function, though.

    The common solution to this is to use xor to find which elements cancel (because there are two of them) and which doesn't. You could also clone the array so destroying the elements doesn't affect the one passed in.


  • 0
    J

    Thank you. Another solution is to sort the array first and find the single one. where can I find the O() of sort function of Arrays?


  • 0
    M

    One of the best possible time complexity is radix sort, using O(n), but its constant makes it slower than the standard O(nlogn) sorts until the size of the array exceeds 2^32 elements. The Arrays.sort() is described here and uses O(nlogn) in many cases, but is still a quicksort so is O(n^2) in the worst case.


  • 0
    J

    Thank you Mike. I really appreciate it.


Log in to reply
 

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