# algorithm - leetcode - single number算法

## 给定一个数字,找到下一个更高的数字,它与原始数字有完全相同的一组数字 (20)

@ BlueRaja算法的JavaScript实现。

``````var Bar = function(num){
num = num.toString();
var max = 0;
for(var i=num.length-2; i>0; i--){
var numArray = num.substr(i).split("");
max = Math.max.apply(Math,numArray);
if(numArray[0]<max){
numArray.sort(function(a,b){return a-b;});
numArray.splice(-1);
numArray = numArray.join("");
return Number(num.substr(0,i)+max+numArray);
}
}
return -1;
};
``````

Very simple implementation using Javascript, next highest number with same digits

``````/*
Algorithm applied
I) Traverse the given number from rightmost digit, keep traversing till you find a digit which is smaller than the previously traversed digit. For example, if the input number is “534976”, we stop at 4 because 4 is smaller than next digit 9. If we do not find such a digit, then output is “Not Possible”.

II) Now search the right side of above found digit ‘d’ for the smallest digit greater than ‘d’. For “534976″, the right side of 4 contains “976”. The smallest digit greater than 4 is 6.

III) Swap the above found two digits, we get 536974 in above example.

IV) Now sort all digits from position next to ‘d’ to the end of number. The number that we get after sorting is the output. For above example, we sort digits in bold 536974. We get “536479” which is the next greater number for input 534976.

*/

function findNext(arr)
{
let i;
//breaking down a digit into arrays of string and then converting back that array to number array
let arr1=arr.toString().split('').map(Number) ;
//started to loop from the end of array
for(i=arr1.length;i>0;i--)
{
//looking for if the current number is greater than the number next to it
if(arr1[i]>arr1[i-1])
{// if yes then we break the loop it so that we can swap and sort
break;}
}

if(i==0)
{console.log("Not possible");}

else
{
//saving that big number and smaller number to the left of it
let smlNum =arr1[i-1];
let bigNum =i;
/*now looping again and checking if we have any other greater number, if we have one AFTER big number and smaller number to the right.
A greater number that is of course greater than that smaller number but smaller than the first number we found.
Why are doing this? Because that is an algorithm to find next higher number with same digits.
*/
for(let j=i+1;j<arr1.length;j++)
{//What if there are no digits afters those found numbers then of course loop will not be initiated otherwise...
if(arr1[j]> smlNum && arr1[j]<arr1[i])
{// we assign that other found number here and replace it with the one we found before
bigNum=j;

}
} //now we are doing swapping of places the small num and big number , 3rd part of alogorithm
arr1[i-1]=arr1[bigNum];
arr1[bigNum]=smlNum;
//returning array
//too many functions applied sounds complicated right but no, here is the  trick
//return arr first then apply each function one by one to see output and then further another func to that output to match your needs
// so here after swapping , 4th part of alogorithm is to sort the array right after the 1st small num we found
// to do that first we simple take part of array, we splice it and then we apply sort fucntion, then check output (to check outputs, pls use chrome dev console)
//and then  simply the rest concat and join to main one digit again.
return arr1.concat((arr1.splice(i,arr1.length)).sort(function(a, b){return a-b})).join('');

// Sorry to make it too long but its fun explaining things in much easier ways as much as possible!!
}

}

findNext(1234);
``````

Since there are lot of comments, so it's better you can copy it to your text editor. 谢谢！

I know this is very old question but still I didn't find easy code in c#. This might help guys who are attending interviews.

``````class Program
{
static void Main(string[] args)
{

int inputNumber = 629;
int i, currentIndexOfNewArray = 0;

int[] arrayOfInput = GetIntArray(inputNumber);
var numList = arrayOfInput.ToList();

int[] newArray = new int[arrayOfInput.Length];

do
{
int temp = 0;
int digitFoundAt = 0;
for (i = numList.Count; i > 0; i--)
{
if (numList[i - 1] > temp)
{
temp = numList[i - 1];
digitFoundAt = i - 1;
}
}

newArray[currentIndexOfNewArray] = temp;
currentIndexOfNewArray++;
numList.RemoveAt(digitFoundAt);
} while (arrayOfInput.Length > currentIndexOfNewArray);

Console.WriteLine(GetWholeNumber(newArray));

}

public static int[] GetIntArray(int num)
{
IList<int> listOfInts = new List<int>();
while (num > 0)
{
num = num / 10;
}
listOfInts.Reverse();
return listOfInts.ToArray();
}

public static double GetWholeNumber(int[] arrayNumber)
{
double result = 0;
double multiplier = 0;
var length = arrayNumber.Count() - 1;
for(int i = 0; i < arrayNumber.Count(); i++)
{
multiplier = Math.Pow(10.0, Convert.ToDouble(length));
result += (arrayNumber[i] * multiplier);
length = length - 1;
}

return result;
}
}
``````

``````34722641
``````

A.将数字序列拆分为两部分，以便在保持降序的同时尽可能长地保留右部分：

``````34722 641
``````

（如果整个号码的顺序是递减的，没有更大的号码可以不添加数字。）

B.1。 选择第一个序列的最后一位数字：

``````3472(2) 641
``````

B.2。 找到第二个序列中比它大的最小数字：

``````3472(2) 6(4)1
``````

B.3。 交换他们：

``````3472(2) 6(4)1
->
3472(4) 6(2)1
->
34724 621
``````

C.按递增顺序排序第二个序列：

``````34724 126
``````

D.完成！

``````34724126
``````

``````/**
*
* Inserts a integer at any index around string.
*
* @param number
* @param position
* @param item
* @return
*/
public String insertToNumberStringAtPosition(String number, int position,
int item) {
String temp = null;
if (position >= number.length()) {
temp = number + item;
} else {
temp = number.substring(0, position) + item
+ number.substring(position, number.length());
}
return temp;
}

/**
* To generate permutations of a number.
*
* @param number
* @return
*/
public List<String> permuteNumber(String number) {
List<String> permutations = new ArrayList<String>();
if (number.length() == 1) {
return permutations;
}
// else
int inserterDig = (int) (number.charAt(0) - '0');
Iterator<String> iterator = permuteNumber(number.substring(1))
.iterator();
while (iterator.hasNext()) {
String subPerm = iterator.next();
for (int dig = 0; dig <= subPerm.length(); dig++) {
inserterDig));
}
}
return permutations;
}
``````

``````1234675
^
``````

``````1234756
``````

``````def PermutationStep(num):
if sorted(list(str(num)), reverse=True) == list(str(num)):
return -1
ls = list(str(num))
n = 0
inx = 0
for ind, i in enumerate(ls[::-1]):
if i < n:
n = i
inx = -(ind + 1)
break
n = i
ls[inx], ls[inx + 1] = ls[inx + 1], ls[inx]

nl = ls[inx::-1][::-1]
ln = sorted(ls[inx+1:])
return ''.join(nl) + ''.join(ln)

print PermutationStep(23514)
``````

``````23541
``````

def PermutationStep（num）

``````a = []
(num.to_s.length).times { a.push("9") }
max_num = a.join('').to_i
verify = num.to_s.split('').sort
matches = ((num+1)..max_num).select {|n| n.to_s.split('').sort == verify }

if matches.length < 1
return -1
else
matches[0]
end
``````

```123456784987654321

123456784 987654321
^the first place from the right where the left-digit is less than the right
Digit "x" is 4

123456784 987654321
^find the smallest digit larger than 4 to the right

123456785 4 98764321
^place it to the left of 4

123456785 4 12346789
123456785123446789
^sort the digits to the right of 5.  Since all of them except
the '4' were already in descending order, all we need to do is
reverse their order, and find the correct place for the '4'
```

``````Sub Main()

Dim Base(0 To 9) As Long
Dim Test(0 To 9) As Long

Dim i As Long
Dim j As Long
Dim k As Long
Dim ctr As Long

Const x As Long = 776914648
Dim y As Long
Dim z As Long

Dim flag As Boolean

' Store the digit count for the original number in the Base vector.
For i = 0 To 9
ctr = 0
For j = 1 To Len(CStr(x))
If Mid\$(CStr(x), j, 1) = i Then ctr = ctr + 1
Next j
Base(i) = ctr
Next i

' Start comparing from the next highest number.
y = x + 1
Do

' Store the digit count for the each new number in the Test vector.
flag = False
For i = 0 To 9
ctr = 0
For j = 1 To Len(CStr(y))
If Mid\$(CStr(y), j, 1) = i Then ctr = ctr + 1
Next j
Test(i) = ctr
Next i

' Compare the digit counts.
For k = 0 To 9
If Test(k) <> Base(k) Then flag = True
Next k

' If no match, INC and repeat.
If flag = True Then
y = y + 1
Erase Test()
Else
z = y ' Match.
End If

Loop Until z > 0

MsgBox (z), , "Solution"

End Sub
``````

``````local number = 564321;

function split(str)
local t = {};
for i = 1, string.len(str) do
table.insert(t, str.sub(str,i,i));
end
return t;
end

local res = number;
local i = 1;
while number >= res do
local t = split(tostring(res));
if i == 1 then
i = #t;
end
t[i], t[i-1] = t[i-1], t[i];
i = i - 1;
res = tonumber(table.concat(t));
end

print(res);
``````

``````public void findNext(int[] nums) {
int i = nums.length - 1;
// nums[i - 1] will be the first non increasing number
while (i > 0 && nums[i] <= nums[i - 1]) {
i--;
}
if (i == 0) {
System.out.println("it has been the greatest already");
} else {
// Find the smallest digit in the second sequence that is larger than it:
int j = nums.length - 1;
while (j >= 0 && nums[j] < nums[i - 1]) {
j--;
}
swap(nums, i - 1, j);
Arrays.sort(nums, i, nums.length);
System.out.println(Arrays.toString(nums));
}
}

public void swap(int[] nums, int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
``````

`38276`排序的数字列表是`23678`

`38627`排序的数字列表是`23678`

O（n）解决方案。 老实说，如果时间只有15分钟，并且需要在白板上完成代码完成，我才会面试失败。

• 避免任何分类。
• 完全避免字符串操作
• 实现O（logN）空间复杂度

``````  public int findNextBiggestNumber(int input  )   {
//take 1358642 as input for example.
//Step 1: split the whole number to a list for individual digital   1358642->[2,4,6,8,5,3,1]
// this step is O(n)
int digitalLevel=input;

List<Integer> orgNumbersList=new ArrayList<Integer>()   ;

do {
Integer nInt = new Integer(digitalLevel % 10);

digitalLevel=(int) (digitalLevel/10  )  ;

} while( digitalLevel >0)    ;
int len= orgNumbersList.size();
int [] orgNumbers=new int[len]  ;
for(int i=0;i<len;i++){
orgNumbers[i ]  =  orgNumbersList.get(i).intValue();
}
//step 2 find the first digital less than the digital right to it
// this step is O(n)

int firstLessPointer=1;
while(firstLessPointer<len&&(orgNumbers[firstLessPointer]>orgNumbers[ firstLessPointer-1 ])){
firstLessPointer++;
}
if(firstLessPointer==len-1&&orgNumbers[len-1]>=orgNumbers[len-2]){
//all number is in sorted order like 4321, no answer for it, return original
return input;
}

//when step 2 step finished, firstLessPointer  pointing to number 5

//step 3 fristLessPointer found, need to find  to  first number less than it  from low digital in the number
//This step is O(n)
int justBiggerPointer=  0 ;

while(justBiggerPointer<firstLessPointer&& orgNumbers[justBiggerPointer]<orgNumbers[firstLessPointer]){
justBiggerPointer++;
}
//when step 3 finished, justBiggerPointer  pointing to 6

//step 4 swap the elements  of justBiggerPointer and firstLessPointer .
// This  is O(1) operation   for swap

int tmp=  orgNumbers[firstLessPointer] ;

orgNumbers[firstLessPointer]=  orgNumbers[justBiggerPointer]  ;
orgNumbers[justBiggerPointer]=tmp ;

// when step 4 finished, the list looks like        [2,4,5,8,6,3,1]    the digital in the list before
// firstLessPointer is already sorted in our previous operation
// we can return result from this list  but  in a differrent way
int result=0;
int i=0;
int lowPointer=firstLessPointer;
//the following pick number from list from  the position just before firstLessPointer, here is 8 -> 5 -> 4 -> 2
//This Operation is O(n)
while(lowPointer>0)        {
result+= orgNumbers[--lowPointer]* Math.pow(10,i);
i++;
}
//the following pick number from list   from position firstLessPointer
//This Operation is O(n)
while(firstLessPointer<len)        {
result+= orgNumbers[firstLessPointer++ ]* Math.pow(10,i);
i++;
}
return  result;

}
``````

``````959879532-->959892357
1358642-->1362458
1234567-->1234576
77654321-->77654321
38276-->38627
47-->74
``````

``````class NumPermExample
{
// print N! permutation of the characters of the string s (in order)
public  static void perm1(String s, ArrayList<String> perm)
{
perm1("", s);
}

private static void perm1(String prefix, String s, ArrayList<String> perm)
{
int N = s.length();
if (N == 0)
{
System.out.println(prefix);
}
else
{
for (int i = 0; i < N; i++)
perm1(prefix + s.charAt(i), s.substring(0, i)
+ s.substring(i+1, N));
}

}

// print N! permutation of the elements of array a (not in order)
public static void perm2(String s, ArrayList<String> perm)
{
int N = s.length();
char[] a = new char[N];
for (int i = 0; i < N; i++)
a[i] = s.charAt(i);
perm2(a, N);
}

private static void perm2(char[] a, int n, ArrayList<String> perm)
{
if (n == 1)
{
System.out.println(a);
return;
}

for (int i = 0; i < n; i++)
{
swap(a, i, n-1);
perm2(a, n-1);
swap(a, i, n-1);
}
}

// swap the characters at indices i and j
private static void swap(char[] a, int i, int j)
{
char c;
c = a[i]; a[i] = a[j]; a[j] = c;
}

// next higher permutation
public static int nextPermutation (int number)
{
ArrayList<String> perm = new ArrayList<String>();

String cur = ""+number;

int nextPerm = 0;

perm1(cur, perm);

for (String s : perm)
{
if (Integer.parseInt(s) > number
&& (nextPerm == 0 ||
Integer.parseInt(s) < nextPerm))
{
nextPerm = Integer.parseInt(s);
}
}

return nextPerm;
}
}
``````

``````public static void main(String[] args)
{
int a = 38276;

int b = NumPermExample.nextPermutation(a);

System.out.println("a: "+a+", b: "+b);
}
``````

``````def findnext(ii): return min(v for v in (int("".join(x)) for x in
itertools.permutations(str(ii))) if v>ii)
``````

``````def findnext(ii):
iis=map(int,str(ii))
for i in reversed(range(len(iis))):
if i == 0: return ii
if iis[i] > iis[i-1] :
break
left,right=iis[:i],iis[i:]
for k in reversed(range(len(right))):
if right[k]>left[-1]:
right[k],left[-1]=left[-1],right[k]
break
return int("".join(map(str,(left+sorted(right)))))
``````

``````#include<bits/stdc++.h>
using namespace std;
int main()
{
int i,j,k,min,len,diff,z,u=0,f=0,flag=0;
char temp[100],a[100]`enter code here`,n;
min=9999;
//cout<<"Enter the number\n";
cin>>a;
len=strlen(a);
for(i=0;i<len;i++)
{
if(a[i]<a[i+1]){flag=1;break;}
}
if(flag==0){cout<<a<<endl;}
else
{
for(i=len-1;i>=0;i--)if(((int)a[i-1])<((int)a[i]))break;
for(k=0;k<i-1;k++)cout<<a[k];
for(j=i;j<len;j++)
{
if(((int)a[j]-48)-((int)a[i-1]-48)>0)
{
diff=((int)a[j]-48)-((int)a[i-1]-48);
if(diff<min){n=a[j];min=diff;}
}
}
cout<<n;
for(z=i-1;z<len;z++)
{
temp[u]=a[z];
u++;
}
temp[u]='\0';
sort(temp,temp+strlen(temp));
for(z=0;z<strlen(temp);z++){if(temp[z]==n&&f==0){f=1;continue;}cout<<temp[z];}
}
return 0;
}
``````

``````function foo(num){
sortOld = num.toString().split("").sort().join('');
do{
num++;
sortNew = num.toString().split("").sort().join('');
}while(sortNew!==sortOld);
return num;
}
``````

``````int t,k,num3,num5;
scanf("%d",&t);
int num[t];
for(int i=0;i<t;i++){
scanf("%d",&num[i]);
}
for(int i=0;i<t;i++){
k=(((num[i]-1)/3)+1);
if(k<0)
printf("-1");
else if(num[i]<3 || num[i]==4 || num[i]==7)
printf("-1");
else{
num3=3*(2*num[i] - 5*k);
num5=5*(3*k -num[i]);
for(int j=0;j<num3;j++)
printf("5");
for(int j=0;j<num5;j++)
printf("3");
}
printf("\n");
}
``````