Java solution: O(n) time and O(1) space: in place sort, swap


  • 0
    T

    Solution: in place sort, swap O(n) time and O(1) space

             **0  1  2  3  4  5  6  7**
               4  3  2  7  8  2  3  1
    i=0        7  3  2  4  8  2  3  1
               3  3  2  4  8  2  7  1 
               2  3  3  4  8  2  7  1
               3  2  3  4  8  2  7  1
    i=1, 2     3  2  3  4  8  2  7  1
    i=2, 3     3  2  3  4  8  2  7  1
    i=3, 4     3  2  3  4  8  2  7  1
    i=4        3  2  3  4  1  2  7  8
               1  2  3  4  3  2  7  8
    i=5 . .         
               1  2  3  4  3  2  7  8
    
    public List<Integer> findDuplicates(int[] A) {
        int n = A.length;
        int tmp=0;
        for (int i=0; i<n; i++) {
            while (A[i]!=i+1 && A[i]!=A[A[i]-1]) {
                tmp = A[i];
                A[i]=A[tmp-1];
                A[tmp-1]=tmp;
            }
    }
    
        List<Integer> res = new ArrayList<>();
        for (int i=0; i<n; i++) {
            if (A[i]!=i+1) res.add(A[i]);
        }
        return res;
    }
    
    

Log in to reply
 

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