每日算法系列【LeetCode 556】下一个更大元素 III

godweiyang

发布于 2020-03-24 10:52:12

5350

发布于 2020-03-24 10:52:12

文章被收录于专栏：算法码上来

题目描述

给定一个32位正整数 n，你需要找到最小的32位整数，其与 n 中存在的位数完全相同，并且其值大于n。如果不存在这样的32位整数，则返回-1。

示例1

输入：
12
输出：
21

示例2

输入：
21
输出：
-1

题解

首先要发现一个性质，如果调换两个数位之后，整个数字变大了，那说明第一个数位的数字小于第二个数位的数。所以我们只需要找到一个顺序对，调换它俩顺序就行了。

但是如果存在两个顺序对和，那我们就要找更大的那个，因为前面的尽量不动才会使调换后的数字最小。

如果相同的话，就要在右边找最小的使得的数，这样处的数字才是最小的，同时整体数字还会变大。

最后因为处已经变大了，所以后面的数字全部都要升序排列，这样整体数字才是最小的。

所以整体算法就有了，我们从右往左找，找到第一个上升的位置，也就是。这样右边就是降序了，不存在顺序对。然后在右边的数字中二分查找最小的大于的数，调换它俩位置。最后把右边的数字变成升序即可。

代码

c++

class Solution {
public:
    int nextGreaterElement(int n) {
        int a[11], len = 0;
        while (n > 0) {
            a[++len] = n % 10;
            n /= 10;
        }
        a[0] = INT_MIN;
        int ok = 0;
        for (int i = 1; i <= len; ++i) {
            if (a[i] < a[i-1]) {
                int idx = upper_bound(a+1, a+i, a[i]) - a;
                swap(a[idx], a[i]);
                for (int j = 1; j <= (i-1)/2; ++j) {
                    swap(a[j], a[i-j]);
                }
                ok = 1;
                break;
            }
        }
        if (!ok) return -1;
        long res = 0;
        for (int i = len; i > 0; --i) {
            res = res * 10 + a[i];
        }
        return res > INT_MAX ? -1 : res;
    }
};

python

class Solution:
    def nextGreaterElement(self, n: int) -> int:
        s = str(n)
        n = len(s)
        res = ''
        for i in range(n-1, -1, -1):
            res = s[i] + res
            if i < n-1 and res[0] < res[1]:
                res = ''.join(sorted(res))
                for j in range(n-i):
                    if res[j] > s[i]:
                        res = res[j] + res[:j] + res[j+1:]
                        break
                s = s[:i] + res
                return int(s) if int(s) < pow(2, 31) else -1
        return -1

后记

这题还可以直接用 c++ 标准库函数 next_permutation 直接生成下一个更大的字符串排列，然后转换成整数就行了，代码如下：

class Solution {
public:
    int nextGreaterElement(int n) {
        string s = to_string(n);
        next_permutation(s.begin(), s.end());
        long res = stoll(s);
        return res > INT_MAX || res <= n ? -1 : res;
    }
};

作者简介：godweiyang，知乎同名，华东师范大学计算机系硕士在读，方向自然语言处理与深度学习。喜欢与人分享技术与知识，期待与你的进一步交流~

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2020-02-07，如有侵权请联系 cloudcommunity@tencent.com 删除

c++

本文分享自算法码上来微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

c++

登录后参与评论

0 条评论

热度