前言
真菜的我。
正文
问题来源
本问题来自leetcode上的556题。用go语言做的
问题描述
给定一个32位正整数 n，你需要找到最小的32位整数，其与 n 中存在的位数完全相同，并且其值大于n。如果不存在这样的32位整数，则返回-1。
示例 1:
输入: 12
输出: 21
示例 2:
输入: 21
输出: -1
分析：
如果从数字的第k位开始到数字尾部都是递减的并且第k位数字比第k-1位数字大，表明从第k位开始到尾部的这段数字是他们能组合出的最大数字，在下一个数字中他们要整体倒序变为能组合出的最小数字，倒序后从这段数字序列中找出第一个大于第k-1位数字的位置和第k-1位交换即可。举个栗子，如果n=13452，其中52是递减的，而且5>4，这样我们先把52倒序，n就变为13425，然后从25中找出第一个大于4的数字和4交换，就得到了最终结果13524。需要注意的是下一个数字可能会超出INT_MAX范围。 本人写的Go代码如下：
const MAX_INT = 2147483647
func reverse(num []byte, b int, e int) {
mid := (b+e-1)/2
for i:=0; b+i<=mid; i++ {
num[b+i],num[e-i] = num[e-i],num[b+i]
}
}
func nextGreaterElement(n int) int {
str := strconv.Itoa(n)
num := []byte(str)
l := len(num)
i := l - 1
for (i != 0) && (num[i] <= num[i-1]) {
i--
}
if i == 0 {
return -1
}
reverse(num, i, l-1)
for j:=i; j<l; j++ {
if num[j] > num[i-1] {
num[j], num[i-1] = num[i-1],num[j]
break
}
}
str = string(num[:])
if (10 == l) && (strings.Compare(str, strconv.Itoa(MAX_INT))>0) {
return -1
}
ret, err := strconv.Atoi(str)
if nil != err {
return -1
}
return ret
}
总结：
勤思考
结语
不管怎么样好好加油。
