前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >每日算法系列【LeetCode 556】下一个更大元素 III

每日算法系列【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

代码语言:javascript
复制
输入:
12
输出:
21

示例2

代码语言:javascript
复制
输入:
21
输出:
-1

题解

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

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

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

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

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

代码

c++

代码语言:javascript
复制
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

代码语言:javascript
复制
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 直接生成下一个更大的字符串排列,然后转换成整数就行了,代码如下:

代码语言:javascript
复制
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 删除

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

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

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

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 题目描述
  • 题解
  • 代码
    • c++
      • python
      • 后记
      相关产品与服务
      NLP 服务
      NLP 服务(Natural Language Process,NLP)深度整合了腾讯内部的 NLP 技术,提供多项智能文本处理和文本生成能力,包括词法分析、相似词召回、词相似度、句子相似度、文本润色、句子纠错、文本补全、句子生成等。满足各行业的文本智能需求。
      领券
      问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档