The solution is accepted but I'm not sure in it's complexity


  • 0
    A

    I've used slightly modified code for Permutations task with the following additions:
    Suppose that we have the following array

    [0_a;0_b;1;1]
    for correct solution we must ensure that items of the same value shouldn't switch places in permutation.
    Basically it means that any of the following is valid

    0_a; 1; 0_b; 1
    1;0_a;0_b;1
    etc
    but this not
    0_b;0_a;1;1

    for enforcing that rule I'm doing simple cycle that checks the following condition:
    If in left part of array there is element with the same value that isn't used in permutation, it means that we trying to broke invariant. Skip this permutation path.
    The code is simple (~75% is reused from basic permutation task), but I still not sure that this is the best way to solve that task.

    public class Permutations2 {
        private boolean[] marked;
        private int[] num;
        private Integer[] currentPermutation;
    
        List<List<Integer>> result = new ArrayList<>();
    
        public List<List<Integer>> permuteUnique(int[] num) {
            marked = new boolean[num.length];
            currentPermutation = new Integer[num.length];
            this.num = num;
    
            Arrays.sort(num);
            permute(0);
    
            return new ArrayList<>(result);
        }
    
        private void permute(int currentIndex) {
            if(currentIndex==num.length) {
                // add the result
                result.add(new ArrayList<>(Arrays.asList(currentPermutation)));
                return;
            }
    
            for (int i = 0; i < num.length; i++) {
    
                // If in left there is an element with the same value but not used in permutation
                // it means that we have case when we 1(at0) 1(at1) try to put 1(at1) before 1(0), and
                // it will generate duplicates.
                // so there is simple check for that case by iterating
                if(!marked[i]) {
                    boolean hasLessNotMarked = false;
                    int j = i-1;
                    while (j>=0 && num[i]==num[j]) {
                        if(!marked[j]) {
                            hasLessNotMarked = true;
                        }
                        j--;
                    }
    
                    if(!hasLessNotMarked) {
                        marked[i] = true;
                        currentPermutation[currentIndex] = num[i];
                        permute(currentIndex + 1);
                        marked[i] = false;
                    }
                }
            }
        }
    }

  • 1
    K

    A python solution using the idea of next_permutation. Note that in this case since we may have duplicates, we use >= to judge the next permutation rather than > as we did in Permutation I:

    class Solution:
    # @param num, a list of integer
    # @return a list of lists of integers
    def permuteUnique(self, num):
        n = len(num)
        if n == 0: return []
        num.sort()
        allists = []
        while True:
            allists.append(num[:])
            p = n-1
            while p > 0 and num[p-1] >= num[p]:
                p -= 1
            if p == 0: break
            q = p
            while q < n and num[q] > num[p-1]:
                q += 1
            # swap
            num[p-1], num[q-1] = num[q-1], num[p-1]
            num[p:] = num[p:][::-1]
        return allists
    

    The complexity of this algorithm is the number of valid unique permutations. Mathematically speaking, suppose we have N elements in the array, with M unique values, hence M <= N. Let D(m) denote the number of duplicates of element m, m = 1, 2, ... M, then the complexity of my algorithm above is:

    N! / (D(1) ! x D(2) ! x D(3)! x ... x D(m)!)

    In the case of no duplicate, i.e., M = N and D(m) = 1 for all m, this algorithm simply reduces to the normal permutation generating algorithm.

    Hope this helps.


Log in to reply
 

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