leetcode Question 70: Permutations II

Permutations II

Given a collection of numbers that might contain duplicates, return all possible unique permutations.
For example,
[1,1,2] have the following unique permutations:
[1,1,2][1,2,1], and [2,1,1].

Analysis:
Facing this kind of problem, just consider this is a similar one to the previous(see here), but need some modifications. In this problem, what we need it to cut some of the subtrees.  e.g. 122
                     122
         /             |           \
     122          212         X  (here because 2=2, we don't need to swap again)
    /     \          /    \
 122   X     212 221

So, if there exist same element after current swap, there there is no need to swap again.
Details see code.


Code:
class Solution {
public:
    bool noswap(int k, int i, const vector<int> num){
        for (int j=k;j<i;j++){
            if (num[j]==num[i]){
                return true;
            }
        }
        return false;
    }

    void perm(vector<int> num,int k,int n, vector<vector<int> > &res){
        if (k==n){
            res.push_back(num);
        }else{
            for (int i=k;i<=n;i++){
                
                if (noswap(k,i,num)){continue;}
                
                int tmp = num[k];
                num[k]=num[i];
                num[i]=tmp;
                
                perm(num,k+1,n,res);
                
                tmp = num[k];
                num[k]=num[i];
                num[i]=tmp;
            }
        }
    }
    vector<vector<int> > permuteUnique(vector<int> &num) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        vector<vector<int> > res;
        perm(num,0,(num.size()-1),res);
        return res;
    }
};

5 comments:

  1. noswap 函数写得很棒,就是不知道为什么要这么写?

    ReplyDelete
    Replies
    1. 这实际上是检查k到i以前有没有和num[i]相同的值。其实不这么写也行,可以用hash set来判重,效率会更高些。

      Delete
    2. 用hashset反而效率变低了 是为什么呢

      Delete

  2. 如果数列的重复个数大于2,例如数列 1,2,2,2就不对了

    ReplyDelete
    Replies
    1. package com.company;

      import java.util.Arrays;
      import java.util.LinkedList;
      import java.util.List;
      import java.util.stream.Collectors;

      public class Solution {

      public static void main(String[] args) {
      // write your code here
      Solution solution = new Solution();
      System.out.println(solution.permuteUnique(new int[]{1, 2, 2, 2}));
      }

      private boolean noswap(int k, int i, int[] num){
      for (int j=k;j> res){
      if (k==n){
      res.add(Arrays.stream(num).boxed().collect(Collectors.toList()));
      }else{
      for (int i=k;i<=n;i++){

      if (noswap(k,i,num)){continue;}

      int tmp = num[k];
      num[k]= num[i];
      num[i] =tmp;

      perm(num,k+1,n,res);

      tmp = num[k];
      num[k]= num[i];
      num[i] = tmp;
      }
      }
      }
      public List> permuteUnique(int[] nums) {
      // Start typing your C/C++ solution below
      // DO NOT write int main() function
      List> res = new LinkedList<>();
      perm(nums,0,(nums.length-1), res);
      return res;
      }
      }


      output:
      [[1, 2, 2, 2], [2, 1, 2, 2], [2, 2, 1, 2], [2, 2, 2, 1]]

      Delete