牛客NC324 下一个更大的数(三)【中等 双指针 Java/Go/PHP/C++】参考lintcode 52 · 下一个排列

题目

题目链接：
https://www.nowcoder.com/practice/475da0d4e37a481bacf9a09b5a059199

思路

第一步：获取数字上每一个数，组成数组arr
第二步：利用“下一个排列” 问题解题方法来继续作答，步骤：利用lintcode 52 下一个排列的解放方法从后往前找，找到第一对(i,j),i<j，使得 nums[i] < num[j] ,然后将两者交换后，后面部分排序即可。

Java代码

import java.util.*;public class Solution {/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可*** @param n int整型* @return int整型*/public int nextGreaterElement (int n) {//lintcode上类似的同一个道题52 · 下一个排列List<Integer> ll = new ArrayList<>();while (n > 0) {int mod = n % 10;n = n / 10;ll.add(mod);}int size = ll.size();int[] arr = new int[size];for (int i = 0; i < size ; i++) {arr[i] = ll.get(size - i - 1);}//利用lintcode 52 下一个排列的解放方法//从后往前找，找到第一对(i,j),i<j，使得 nums[i] < num[j] ,//然后将两者交换后，后面部分排序即可。for (int i = size - 1; i >= 0 ; i--) {for (int j = size - 1; j > i ; j--) {if (arr[i] < arr[j]) {int t = arr[i];arr[i] = arr[j];arr[j] = t;Arrays.sort(arr, i + 1, size);String s = "";for (int i1 : arr) {s += i1;}//这个位置lintcode52是return arrreturn Integer.valueOf(s);}}}return -1; //这个位置lintcode52是return 排序后的arr}
}

Go代码

package mainimport "sort"/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可*** @param n int整型* @return int整型*/
func nextGreaterElement(n int) int {//类似的题目是lintcode 52下一个排列ll := []int{}for n > 0 {mod := n % 10n = n / 10ll = append(ll, mod)}size := len(ll)arr := make([]int, size)for i := 0; i < size; i++ {arr[i] = ll[size-i-1]}//利用lintcode 52 下一个排列的解放方法//从后往前找，找到第一对(i,j),i<j，使得 nums[i] < num[j] ,//然后将两者交换后，后面部分排序即可。for i := size - 1; i >= 0; i-- {for j := size - 1; j > i; j-- {if arr[i] < arr[j] {t := arr[i]arr[i] = arr[j]arr[j] = tarr1 := []int{}if i+1 < size {for k := i + 1; k < size; k++ {arr1 = append(arr1, arr[k])}}sort.Ints(arr1) //对i+1开始到最后的数字进行排序ans := 0for k := 0; k <= i; k++ {ans = ans*10 + arr[k]}for k := 0; k < len(arr1); k++ {ans = ans*10 + arr1[k]}return ans}}}return -1
}

PHP代码

<?php/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param n int整型 * @return int整型*/
function nextGreaterElement( $n )
{//类似的同一道题是lintcode 52 下一个排列$arr = [];while ($n >0){$mod = $n%10;$n =intval($n/10);array_unshift($arr,$mod);}//利用lintcode 52 下一个排列的解放方法//从后往前找，找到第一对(i,j),i<j，使得 nums[i] < num[j] ,//然后将两者交换后，后面部分排序即可。$size = count($arr);for($i=$size-1;$i>=0;$i--){for($j=$size-1;$j>$i;$j--){if($arr[$i] < $arr[$j]){$t = $arr[$i];$arr[$i] = $arr[$j];$arr[$j]= $t;$arr1 = [];for($k=$i+1;$k<$size;$k++){array_push($arr1,$arr[$k]);}sort($arr1); //对i+1到size位置的数排序$ans = 0;for($k=0;$k<=$i;$k++){$ans = $ans*10+$arr[$k];}for($k=0;$k<count($arr1);$k++){$ans =$ans*10+$arr1[$k];}return $ans;}}}return -1;
}

C++代码

class Solution {public:/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可*** @param n int整型* @return int整型*/int nextGreaterElement(int n) {vector<int> ll;while (n > 0) {ll.push_back(n % 10);n = n / 10;}int size = ll.size();vector<int> arr(size);for (int i = 0; i < size; i++) {arr[i] = ll[size - i - 1];}//利用lintcode 52 下一个排列的解放方法//从后往前找，找到第一对(i,j),i<j，使得 nums[i] < num[j] ,//然后将两者交换后，后面部分排序即可。for (int i = size - 1; i >= 0; i--) {for (int j = size - 1; j > i; j--) {if (arr[i] < arr[j]) {int t = arr[i];arr[i] = arr[j];arr[j] = t;std::sort(arr.begin() + i + 1, arr.end()); //对i+1到size位置的数排序int ans = 0;for (int k = 0; k < size; k++) {ans = ans * 10 + arr[k];}return ans;}}}return -1;}
};