556. Next Great Element III

发表于 | 分类于

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
2
Input: 12
Output: 21

Example 2:

1
2
Input: 21
Output: -1

解法1：

用next permutation的算法来解，先把n转换成一个数字的数组，然后接下的算法就是一致的了。
要注意的是算出来的答案可能会overflow,所以要判断一下是否overflow。
C++

1

Java

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
49
50
51
52
53
54
55
public class Solution {
    public int nextGreaterElement(int n) {
        int len = (int)Math.log10(n) + 1;
        int[] digits = new int[len];
        int i = len - 1;
        while (n > 0) {
            digits[i--] = n % 10;
            n /= 10;
        }
        // Use the next permutation algorithm
        int pivot = -1;
        for (i = len - 2; i >= 0; i--) {
            if (digits[i] < digits[i + 1]) {
                pivot = i;
                break;
            }
        }
        if (pivot == -1) {
            return -1;
        }
        for (i = len - 1; i > pivot; i--) {
            if (digits[i] > digits[pivot]) {
                int temp = digits[i];
                digits[i] = digits[pivot];
                digits[pivot] = temp;
                break;
            }
        }
        int j;
        for (i = pivot + 1, j = len - 1; i < j; i++,j--) {
            int temp = digits[i];
            digits[i] = digits[j];
            digits[j] = temp;
        }
        // combine
        int res = 0;
        for (i = 0; i < len; i++) {
            if (res > Integer.MAX_VALUE / 10 || (res == Integer.MAX_VALUE / 10 && res % 10 > Integer.MAX_VALUE % 10)) {
                return -1;
            }
            res = res * 10 + digits[i];
        }
        return res;
    }
}