题目链接

LeetCode

题目描述

给你一个正整数 n ，请你找出符合条件的最小整数，其由重新排列 n中存在的每位数字组成，并且其值大于 n 。如果不存在这样的正整数，则返回 -1 。

注意 ，返回的整数应当是一个 32 位整数 ，如果存在满足题意的答案，但不是 32 位整数 ，同样返回 -1 。

示例 1：

输入： n = 12
输出： 21

示例 2：

输入： n = 21
输出： -1

提示：

  • 1 <= n <= 231 - 1

    解题思路

    方法一：排序

    1. class Solution {
    2.   public int nextGreaterElement(int n) {
    3.       String s = String.valueOf(n);
    4.       char[] arr = s.toCharArray();
    5.       int len = arr.length;
    6.       int i;
    7.       // 找到arr[i-1] < arr[i]
    8.       for(i = len - 1; i > 0; --i){
    9.           if(arr[i] > arr[i - 1]){
    10.               break;
    11.           }
    12.       }
    13.       if(i > 0 && arr[i] > arr[i - 1]){
    14.           int pos = i;
    15.           // 找到大于arr[i-1]的最小值
    16.           for(int j = i; j < len; ++j){
    17.               if(arr[j] < arr[pos] && arr[j] > arr[i - 1]){
    18.                   pos = j;
    19.               }
    20.           }
    21.           // 交换
    22.           char tmp = arr[pos];
    23.           arr[pos] = arr[i - 1];
    24.           arr[i - 1] = tmp;
    25.       }else{
    26.           return -1;
    27.       }
    28.       // i-1后面的从小到大排序
    29.       char[] tmpArr = new char[len - i];
    30.       for(int j = 0; j < tmpArr.length; ++j){
    31.           tmpArr[j] = arr[j + i];
    32.       }
    33.       Arrays.sort(tmpArr);
    34.       for(int j = 0; j < tmpArr.length; ++j){
    35.           arr[j + i] = tmpArr[j];
    36.       }
    37.       long res = 0;
    38.       for(char c : arr){
    39.           res = res * 10 + c - '0';
    40.           if(res > Integer.MAX_VALUE){
    41.               return -1;
    42.           }
    43.       }
    44.       return (int)res;
    45.   }
    46. }

  • 时间复杂度 O(m^2n)

  • 空间复杂度 O(mn)