Code & Func

第9天了。

Given a positive 32-bit integer n, you need to find the smallest 32-bit integer which has exactly the same digits existing in the integer n and is greater in value than n. If no such positive 32-bit integer exists, you need to return -1.

Example 1:

1
Input: 12
2
Output: 21

Example 2:

1
Input: 21
2
Output: -1

这道题我的解法是：

先将数字转换成数组，由于是除法和取余解析出来的数组，所以整个数组是倒过来的，即123得到[3,2,1]
从前向后遍历找到第一个逆序（即vec[i-1] > vec[i)的情况。
从vec[0: i]找到第一个小于等于vec[i]的元素vec[j]。
交换vec[i]和vec[j]，然后将vec[0: i]逆序。
将vec转换回数字，最后判断一下是否溢出即可。

1
int nextGreaterElement(int n) {
2
    long res = 0;
3
    vector<int> vec;
4
    while(n) {
5
        vec.push_back(n % 10);
6
        n /= 10;
7
    }
8
    int i, j;
9
    for(i = 1;i < vec.size() && vec[i-1] <= vec[i] ;++i) {
10

11
    }
12
    if (i == vec.size()) return -1;
13

14
    for(j = 0;vec[i] >= vec[j];++j) {
15

13 collapsed lines
16
    }
17
    swap(vec[i], vec[j]);
18
    for(j = 0, i = i - 1; j < i; j++, i--) {
19
        swap(vec[i], vec[j]);
20
    }
21

22
    for(i = vec.size() -1;i >= 0; i--) {
23

24
        res = res * 10 + vec[i];
25
    }
26
    if (res > INT_MAX) return -1;
27
    return res;
28
}

其实写到这里基本上发现，这道题就是找全排列中的下一个元素，而这个功能，在C++中提供了一个好用的函数：next_permutation，所以我们可以先用to_string转换成字符数组，然后用next_permutation来解这道题：

1
int nextGreaterElement(int n) {
2
    string s = to_string(n);
3
    if (next_permutation(s.begin(), s.end())) {
4
        long temp = atol(s.c_str());
5
        if (temp <= INT_MAX)  return temp;
6
        else return -1;
7
    }
8
    return -1;
9
}