Accepted Solution with duplicate value swapping. Linear?


  • 0
    D

    I use the array and a created boolean to track non-duplicate elements. I swap found duplicate values from the next element in the array to the found duplicate element's location, then leap the next element in the search. This code was accepted but I don't think it's linear. Does this meet the timing and memory objectives?

    The Solutions Runtime: 900ms

    public int singleNumber(int[] A) {
        for (int i = 0; i < A.length - 2; i++) {
            boolean dupe = false;
            
            for(int j = i + 1; j < A.length; j++) {
                if (A[i] == A[j]) {                    
                    A[j] = A[++i];
                    dupe = true;
    
                    break;
                }
            }
            
            if (!dupe) return A[i];
        }
    
        return A[A.length - 1];
    }

  • 0
    M

    No, this code is of O(N^2) complexity. Even though it is right but it is not the solution to the question.


  • 0
    J

    I believe in leetcode, every question represents a typical problem and has corresponding algorithm. However, I am just curious, how can we know the intended algorithm? For example, this problem can be solved by the XOR operation. Is this the intended algorithm?


  • 0
    M

    I'm afraid I would have to tell you what others have been saying for years.. There is no unique solution to a programming question. What you can do is, check out available solutions of others who have done it, then you can have an idea of how you could have solved the question in a different manner and learn from other possible algorithms of solving questions. This is how I use leetcode to my benefit.


Log in to reply
 

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