题目

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].

方法

和上一题的方法一样，利用nextPermutation的思想。http://blog.csdn.net/u010378705/article/details/31348875

	private boolean isReverseOrder(int[] num) {
		for (int i = 0; i < num.length - 1; i++) {
			if (num[i] < num[i + 1]) {
				return false;
			}
		}
		return true;
	}
    public List
   
    > permuteUnique(int[] num) {
    	List
    
     > list = new ArrayList
     
      >(); if (num == null || num.length == 0) { return list; } Arrays.sort(num); while (!isReverseOrder(num)) { List
      
        subList = new ArrayList
       
        (); for (int i = 0; i < num.length; i++) { subList.add(num[i]); } list.add(subList); nextPermutation(num); } List
        
          subList = new ArrayList
         
          (); for (int i = 0; i < num.length; i++) { subList.add(num[i]); } list.add(subList); nextPermutation(num); return list; } public void nextPermutation(int[] num) { if (num != null && num.length != 0 && num.length != 1) { int len = num.length; int i = len; for (; i > 1; i--) { if (num[i - 1] > num[i - 2]) { int flag = 0; for (int k = i - 1; k < len; k++) { if (num[k] <= num[i - 2]) { flag = k - 1; break; } } if (flag == 0) { flag = len - 1; } int temp = num[flag]; num[flag] = num[i - 2]; num[i - 2] = temp; Arrays.sort(num, i - 1, len); break; } } } }