leetcode: Permutations

问题描述：

Given a collection of distinct numbers, return all possible permutations.

For example,
[1,2,3] have the following permutations:
[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], and [3,2,1].

原问题链接：https://leetcode.com/problems/permutations/

 

问题分析

　　这个问题可以归结为典型的排列问题。在之前的一篇文章里有过详细的讨论。 在前面的文章里，我们提到的字典序排列的方法就可以很好的解决这个问题。在每次生成字典序的排列最后我们将这个序列加入到List里面，这样就可以得到所有的排列生成列表。

　　而字典序排列的过程概括起来就是如下这么个步骤：

1. 找最后面的连续递增点。
2. 根据找到的点后面找最接近的大于它的元素。
3. 倒置后面序列里的元素。

　　详细实现见如下代码：

 

public class Solution {
    public List<List<Integer>> permute(int[] num) {
        Arrays.sort(num);
        List<List<Integer>> lists = new ArrayList<List<Integer>>();
        lists.add(appendList(num));
        while(true) {
            int start = findStart(num);
            if(start == -1) break;
            int end = findEnd(num, start);
            if(end == -1) break;
            swap(num, start, end);
            reverse(num, start + 1, num.length - 1);
            lists.add(appendList(num));
        }
        return lists;
    }
    
    private List<Integer> appendList(int[] num) {
        List<Integer> list = new ArrayList<Integer>();
        for(int i = 0; i < num.length; i++)
            list.add(num[i]);
        return list;
    }
    
    private int findStart(int[] num) {
        for(int i = num.length - 2; i >= 0; i--)
            if(num[i] < num[i + 1])
                return i;
        return -1;
    }
    
    private int findEnd(int[] num, int l) {
        for(int i = num.length - 1; i > l; i--)
            if(num[i] > num[l])
                return i;
        return -1;
    }
    
    private void reverse(int[] num, int l, int r) {
        while(l < r) {
            swap(num, l, r);
            l++;
            r--;
        }
    }
    
    private void swap(int[] num, int i, int j) {
        int temp = num[i];
        num[i] = num[j];
        num[j] = temp;
    }
}