31. 下一个排列

题意：

解题思路：

思路：
    1,2,3 → 1,3,2
    3,2,1 → 1,2,3
    1,1,5 → 1,5,1
        index:1
    1  2  7  4  3  1  //右到左第一个逆序的数字 是 2
    1  2  7  4  3  1  //右到左第一个比逆序的数字大的数字 是 3
    1  3  7  4  2  1  // 2 和 3 交换 
    1  3  7  4  2  1  //index之后的数字翻转
        index   
    1  3  1  2  4  7

PHP代码实现：

class Solution {
    function nextPermutation(&$nums) {
        $n = count($nums);
        for ($i = $n - 1; $i >= 0; $i--) {
            if ($nums[$i + 1] > $nums[$i]) {
                for ($j = $n - 1; $j >= 0; $j--) {
                    if ($nums[$j] > $nums[$i]) {
                        break;
                    }
                }
                $temp = $nums[$i];
                $nums[$i] = $nums[$j];
                $nums[$j] = $temp;
                $left = $i + 1;
                $right = $n - 1;
                return $this->reverse($nums, $left, $right);
            }
        }
        return $this->reverse($nums, 0, $n - 1);
    }
    function reverse(&$nums, $left, $right) {
        while ($left < $right) {
            $temp = $nums[$left];
            $nums[$left] = $nums[$right];
            $nums[$right] = $temp;
            $left ++;
            $right --;
        }
    }
    function swap(&$nums, $i, $j) {
        $tmp = $nums[$i];
        $nums[$i] = $nums[$j];
        $nums[$j] = $tmp;
    }
    function nextPermutation1(&$nums) {
        if ($nums == null || count($nums) < 2) return;
        $n = count($nums);
        $p = $n - 2;
        while ($p >= 0 && $nums[$p] >= $nums[$p+1]) --$p;
        if ($p >= 0) {
            $i = $n - 1;
            while ($i > $p && $nums[$i] <= $nums[$p]) --$i;
            $this->swap($nums, $i, $p); 
        }
        for ($i = $p+1, $j = $n-1; $i < $j; ++$i,--$j)
            $this->swap($nums, $i, $j);
    }
}

GO代码实现：

func nextPermutation(nums []int)  {
    n := len(nums)
    i, j := n-2, n-1
    // 从右往左找到第一个非递增的数
    for ; i >= 0; i-- { 
        if nums[i+1] > nums[i] {
            break
        }
    }
    if i < 0 {
         reverse(nums)
         return
    }
    // 从右往走找到第一个比nums[i]大的数
    for ; j >= 0; j-- {
        if nums[j] > nums[i] {
            break
        }
    }
    nums[j], nums[i] = nums[i], nums[j] 
    // 将非递增位置之后的反转成为从右往走递减序列
    reverse(nums[i+1:n]) 
}
func reverse(nums []int) {
    l, r := 0, len(nums)-1
    for l <= r {
        nums[l], nums[r] = nums[r], nums[l]
        l, r = l+1, r-1
    }
}