LeetCode 31. 下一个排列

31. 下一个排列

整数数组的一个 排列 就是将其所有成员以序列或线性顺序排列。
例如，arr = [1,2,3] ，以下这些都可以视作 arr 的排列：[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1] 。
整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。更正式地，如果数组的所有排列根据其字典顺序从小到大排列在一个容器中，那么数组的 下一个排列 就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列，那么这个数组必须重排为字典序最小的排列（即，其元素按升序排列）。
例如，arr = [1,2,3] 的下一个排列是 [1,3,2] 。
类似地，arr = [2,3,1] 的下一个排列是 [3,1,2] 。
而 arr = [3,2,1] 的下一个排列是 [1,2,3] ，因为 [3,2,1] 不存在一个字典序更大的排列。
给你一个整数数组 nums ，找出 nums 的下一个排列。
必须 原地 修改，只允许使用额外常数空间。

方法一、两边扫描

下一排列必然大于当前排列，如[1, 2, 3]的下一排列[1, 3, 2]
比较直观的发现是交换了两个数，我们称被交换的数为最小数和最大数，那如何求解最小数最大数呢？

通过观察我们发现，对于长度为n的排列a：
1.首先从后向前找出第一个顺序对(i, i+1),使得nums[i]<nums[i+1],这个i位置就是最小数
2.同理，我们从后向前找出j，使得nums[j] > nums[i], j位置就是最大数，交换i和j位置的元素
3.在此过程中，我们还需要保证变大的幅度尽可能小，i+1位置开始升序排列可保证变大的幅度小，注意到i+1位置开始后续都是倒序排列，因此直接用双指针交换即可，不用排序

Swift

func nextPermutation(_ nums: inout [Int]) {
        let cnt = nums.count
        
        //从右向左找出i，使得nums[i] < nums[i+1]
        var i = cnt - 2
        while i>=0 && nums[i] >= nums[i+1] {
            i -= 1
        }
        
        if i >= 0 {//i 存在，则从右向左找出j，使得nums[j] > nums[i]
            var j = cnt-1
            while j >= 0 && nums[j] <= nums[i] {
                j -= 1
            }
            
            //交换i和j
            nums.swapAt(i, j)
        }
        
        //i+1位置开始，升序排列，以保证变大的幅度尽可能小。由于题目要求必须 原地 修改，只允许使用额外常数空间。因此使用双指针操作
        i = i + 1
        var j = cnt-1
        while i < j {
            nums.swapAt(i, j)
            
            i += 1
            j -= 1
        }
    }

OC

- (void)nextPermutation:(NSMutableArray *)nums {
    NSInteger cnt = nums.count;
    
    NSInteger i = cnt - 2;
    while (i >= 0 && [nums[i] integerValue] >= [nums[i+1] integerValue]) {
        i--;
    }
    
    if (i >= 0) {
        NSInteger j = cnt - 1;
        while (j >= 0 && [nums[j] integerValue] <= [nums[i] integerValue]) {
            j--;
        }
        
        [nums exchangeObjectAtIndex:i withObjectAtIndex:j];
    }
    
    i = i + 1;
    NSInteger j = cnt - 1;
    while (i < j) {
        [nums exchangeObjectAtIndex:i withObjectAtIndex:j];
        
        i++;
        j--;
    }
}