LeetCode 31. Next Permutation [Swift 题解]

题目

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 and use only constant 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  

题意: 把这个数里数字打乱顺序,找到下一个刚好大过原数的数字。如果原数已经是最大值,则返回最小可能数。

附: 原题目链接

思路

题目里的edge case 是这个数已经是最大可能的数, 看一下规律,按位数看的话左边的数字应该是不小于右边的数字的, 如54321。

比如给定现在数字为12642, 则我们的目标数字为14226, 现在来看一下12642->14226是怎么转换的。

第一步,找出这个千位数上的2为我们将要替换的数字,怎么找出来呢,如果从右边的位数依次往左看,你会发现这个2是第一个不再按升序排序的数字(从个数2->4->6->2)

第二步,找出与之替换的数字,怎么找呢,应该是从右边位数依次查找出第一个大于2的那个数(4,在十位), 将之替换, 则现在的结果是14622

第三步, 14622 -> 14226 要怎么转换呢, 可以看到其实是4之后的数字(622)进行逆序得到(226)

依据这三个步骤,可以写出如下代码:

class Solution {  
    func nextPermutation(_ nums: inout [Int]) {
        guard nums.count > 2 else {
            rev(&nums, low: 0, high: nums.count - 1)
            return
        }

        let end = nums.count - 2
        var k: Int?
        var l: Int?
        for index in (0...end).reversed() {
            if nums[index] < nums[index+1] {
                k = index
                break
            }
        }

        if k == nil {
            rev(&nums, low: 0, high: nums.count - 1)
            return
        }

        for index in ((k!+1)...(nums.count-1)).reversed() {
            if nums[index] > nums[k!] {
                l = index
                break
            }
        }

        nums.swapAt(k!, l!)
        rev(&nums, low: k!+1, high: nums.count - 1)
    }


    private func rev(_ nums: inout [Int], low: Int, high: Int) {
        var _low = low
        var _high = high
        while _low < _high {
            nums.swapAt(_low, _high)
            _low += 1
            _high -= 1
        }
    }
}

chenbo

编程爱好者

Singapore