[leetcode]Next Permutation

怎么说呢，这篇博文的算法还是很不错的，新博文采用的还是这篇博文的就算法，只不过代码更简洁，可能读可能更好一点，有兴趣请移步，新博文地址：[leetcode]Next Permutation

Next Permutation

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).

The replacement must be in-place, do not allocate extra memory.

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

 给你一个数字组成的字符串，这组数字可以排列成大概n！个数字（当有重复数字的时候，排列数< n!）结果要求你返回排列中原字符串的后驱数字。

例如123可以组成123,132,213,231,312,321，其中132是123的后驱，同理213是132的后驱，当321达到最大时，则返回最小的排列情况123，最为其后驱。

这道题比较折腾，做了很长时间。

我的算法首先必须从后往前遍历。原因很明显，请往下看：

1. 从后往前遍历，找到临界点。

1.1 如果发现某个位置，前面的数字变小了。比如132中，1比3小，则1就是临界点。

1. 2 如果数字越来越大，比如321。2比1，3比2大，则这个数是最大的。这是显然的。标记之。

 

2.从1后面的3开始往后遍历，找到比1大的最小的数字，本例中是2。然后将2与1交换。这时数字变成了231

3.对2后面的所有数字做排序，即对31做排序，得到13，最终结果是213。

这下大家就很明显的看出来为什么必须从后往前遍历。

代码如下：

    public void nextPermutation(int[] num) {
        if(num == null || num.length <= 1){
        	return;
        }
        boolean tag = true;
        for(int i = num.length - 1; i > 0 ; i--){
        	if(num[i] > num[i - 1]){
        		for(int j = i ; j < num.length; j++){
        			if(num[j] > num[i - 1] && (j == num.length - 1 || num[j + 1] <= num[i - 1]  )){
        				int tem = num[j];
        				num[j] = num[i - 1] ;
        				num[i - 1] = tem;
        				break;
        			}
        		}
        		int[] copy = Arrays.copyOfRange(num, i ,num.length);
        		Arrays.sort(copy);
        		for(int j = i; j < num.length; num[j] = copy[j - i],j++);
        		tag = false;//标记找到了临界点
        		break;
        	}
        }    
        if(tag){//如果没有找到临界点，则该排列数是最大的，变为最小的即可
        	for(int i = 0; i < num.length / 2; i++){
        		int temp = num[i];
        		num[i] = num[num.length - 1 - i];
        		num[num.length - 1 - i] = temp;
        	}
        }
    }