leetcode解法: Next Permutation (31)

发表于 | 分类于

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,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

解法1： O(N) Time

一个固定的解法,可以写出来几个答案然后从当中找结论.
解法是:
从右往左找到第一个数字使得num[i] < num[i + 1], 设i为pivot
从右往左找到第一个数字使得num[j] > num[pivot], 记录j
将pivot和j指向的item互换
将pivot右边的数组reverse

要注意的是,在第二步中由于pviot右面的数组一定是sorted(从大到小), 所以我们在寻找第一个比pivot数字大的时候可以采用binary search来提供一些小的optimization.

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        
        if (nums.size() <= 1) {
            return;
        }
        
        int pivot = -1;
        for (int i = nums.size() - 1; i >= 1; --i) {
            if (nums[i - 1] < nums[i]) {
                pivot = i - 1;
                break;
            }
        }
        
        if (pivot == -1) {
            std::reverse(nums.begin(), nums.end());
            return;
        }
        
        // find the first element that is larger than nums[pivot]
        int ex = bsearch(nums, pivot + 1, nums.size() - 1, nums[pivot]);
        int temp = nums[pivot];
        nums[pivot] = nums[ex];
        nums[ex] = temp;
        
        // reverse ex + 1 ~ end
        std::reverse(nums.begin() + pivot + 1, nums.end());
        return;
        
    }
    
    int bsearch(vector<int>& nums, int start, int end, int ref) {
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (nums[mid] > ref) {
                start = mid;
            } else {
                end = mid;
            }
        }
        if (nums[end] > ref) {
            return end;
        }
        return start;
    }
};

Java

1