Given a positive 32-bit integer n, you need to find the smallest 32-bit integer which has exactly the same digits existing in the integer n and is greater in value than n. If no such positive 32-bit integer exists, you need to return -1.
Example 1:
Input: 12 Output: 21
Example 2:
Input: 21 Output: -1
A:
就是转成long然后对比呗
class Solution { public: int nextGreaterElement(int n) { vector<int> V; while(n){ V.push_back(n%10); n = n/10; } int cDigit = V.size(); int smallerIndex = -1; for(int i =1;i<cDigit;i++){ if(V[i]<V[i-1]){ smallerIndex = i; break; } } if(smallerIndex<0) return -1; // first the first place that's smaller than smallerIndex; int firstBigger = -1; for(int i =0;i<smallerIndex;i++){ if(V[i]>V[smallerIndex]){ firstBigger = i; break; } } int tmp = V[smallerIndex]; V[smallerIndex] = V[firstBigger]; V[firstBigger] = tmp; // swap all int start = 0, end = smallerIndex-1; while(start<end){ tmp = V[start]; V[start] = V[end]; V[end] = tmp; start++; end--; } long res = 0; while(not V.empty()){ int last = V.back(); V.pop_back(); res = res * 10 + last; } if(res > INT_MAX) return -1; return (int)res; } };
No comments:
Post a Comment