私はちょうどインタビューを爆撃し、インタビューの質問でほとんど進歩を遂げませんでした。誰かがこれを行う方法を教えてもらえますか？オンラインで検索しようとしましたが、何も見つかりませんでした。
番号を指定して、元の番号とまったく同じ数字のセットを持つ次に大きい番号を見つけます。例：与えられた38276は38627を返します
最初に、1桁よりも小さい最初の桁（右から）のインデックスを見つけたいと思いました。次に、サブセットの最後の桁をローテーションして、同じ桁で構成される次の最大数になるようにしましたが、スタックしました。
インタビュアーはまた、一度に1つずつ数字を交換することを提案しましたが、アルゴリズムを理解できず、画面を20〜30分ほど見つめていました。言うまでもなく、就職活動を続けなければならないと思います。
編集：その価値のために、私は次のインタビューに招待されました
O(n)次のように（n桁数は）で実行できます。
右から始めて、左の桁が右の桁よりも小さくなるような最初の桁のペアを見つけます。左桁を「digit-x」で参照してみましょう。Digit-xの右側にあるdigit-xより大きい最小の数値を見つけて、digit-xのすぐ左に配置します。最後に、残りの数字を昇順で並べ替えます。すでに降順であるため、逆にするだけです（digit-xを保存します。これは、の正しい場所に配置できますO(n)）。
例はこれをより明確にします：
123456784987654321
数字で始める
123456784 987654321
^左桁が右よりも小さい右から1番目の場所
数字「x」は4です
123456784 987654321
^右に4より大きい最小の数字を見つけます
123456785 4 98764321
^4の左側に配置します
123456785 4 12346789
123456785123446789
^5の右側の数字を並べ替えます。
「4」はすでに降順でした。必要なのは
順序を逆にして、「4」の正しい場所を見つけます
正当性の証明：
大文字を使用して数字列と数字の小文字を定義しましょう。構文は、 「文字列とABの連結」を意味します。 は辞書式順序です。これは、数字列の長さが等しい場合の整数順序と同じです。AB<
元の数値Nは、の形式AxBです。ここxで、は1桁で、B降順でソートされます。
アルゴリズムによって検出された数値はAyC、です。ここy ∈ Bで、は最小の桁> x であり（選択された方法により存在する必要があります。x上記を参照）、C昇順で並べ替えられます。
N'のような数（同じ数字を使用）があると仮定しAxB < N' < AyCます。 N'で始まる必要があります。Aそうでない場合は、それらの間に収まらないため、フォームで記述できますAzD。これで、不等式はAxB < AzD < AyC、になります。これは、xB < zD < yC3つの数字列すべてに同じ数字が含まれている場合と同じです。
それが真実であるためには、私たちはを持っている必要がありますx <= z <= y。yは最小の数字なので> x、zそれらの間に置くことはできません。したがって、z = xまたはz = y。言うz = x。次に、不等式はです。これは、との両方が同じ桁xB < xD < yCであることを意味します。ただし、Bは降順でソートされるため、これらの桁がそれよりも大きい文字列はありません。したがって、を持つことはできません。同じ手順に従うと、が、を持つことができないことがわかります。B < DBDB < Dz = yD < C
したがってN'、存在することはできません。これは、アルゴリズムが次に大きい数を正しく検出することを意味します。
ほぼ同じ問題がCodeJamの問題として現れ、ここに解決策があります。
http://code.google.com/codejam/contest/dashboard?c=186264#s=a&a=1
例を使用したメソッドの概要は次のとおりです。
34722641
A.数字のシーケンスを2つに分割して、右側の部分ができるだけ長くなり、降順のままになるようにします。
34722 641
（数字全体が降順の場合、数字を追加せずに大きな数字を作成することはできません。）
この時点で、左側の部分から始まる大きな数字はないことがわかります。これは、右側の部分が残りの桁ですでに可能な限り大きいためです。
B.1。最初のシーケンスの最後の桁を選択します。
3472(2) 641
B.2。2番目のシーケンスでそれよりも大きい最小の数字を見つけます。
3472(2) 6(4)1
あなたがしていることは、左側の部分への可能な限り最小の増加を見つけることです。
B.3。それらを交換します：
3472(2) 6(4)1
->
3472(4) 6(2)1
->
34724 621
C.2番目のシーケンスを昇順で並べ替えます。
34724 126
D.完了！
34724126
同じ左の部分で大きな数がないことがわかるように数を分割し、左の部分を可能な限り少なくし、残りの右の部分をできるだけ小さくしたので、この新しい数を確認できます同じ数字のコレクションで作成できる最小の大きい数です。
これがPythonのコンパクトな（しかし部分的にブルートフォースの）ソリューションです
def findnext(ii): return min(v for v in (int("".join(x)) for x in
itertools.permutations(str(ii))) if v>ii)
C ++では、次のような順列を作成できます：https : //stackoverflow.com/a/9243091/1149664（itertoolsのアルゴリズムと同じアルゴリズムです）
これは、WeebleとBlueRajaによって説明されたトップアンサーの実装です（他のアンサー）。もっと良いものがあるとは思えません。
def findnext(ii):
iis=list(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)))))
少なくとも、ブルートフォースストリングベースのソリューションの例をいくつか示します。これは、頭のてっぺんから思いつくことができたはずです。
38276ソートされた数字のリストは23678
38627ソートされた数字のリストは23678
ブルートフォースの増分、並べ替え、比較
ブルートフォースソリューションに沿って文字列に変換され、ブルートフォースはそれらの数字を使用してすべての可能な数値を使用します。
それらすべてからintを作成し、それらをリストに入れて並べ替え、ターゲットエントリの次のエントリを取得します。
あなたがこれに30分を費やし、少なくともブルートフォースアプローチを思い付かなかった場合、私もあなたを雇うことはありません。
ビジネスの世界では、エレガントではなく、遅くて不格好であるが、仕事を成し遂げるソリューションは、ソリューションがまったくない場合よりも常に価値があります。実際、すべてのビジネスソフトウェアについて、エレガントでなく、遅くて不格好です。
function foo(num){
sortOld = num.toString().split("").sort().join('');
do{
num++;
sortNew = num.toString().split("").sort().join('');
}while(sortNew!==sortOld);
return num;
}
あなたのインタビュアーがあなたをこのようなものに向かって優しく押し込もうとしていたと私はかなり確信しています：
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);
必ずしも最も効率的または洗練されたソリューションではありませんが、提供された例を2サイクルで解決し、彼が提案したように一度に1つずつ数字を交換します。
あなたの案
最初に、1桁よりも小さい最初の桁（右から）のインデックスを見つけたいと思いました。次に、サブセットの最後の桁をローテーションして、同じ桁で構成される次の最大数になるようにしましたが、スタックしました。
実際、かなり良いです。最後の桁だけでなく、現在考慮されているよりも重要性の低いすべての桁を考慮する必要があります。その前に、単調な数字のシーケンスがあります。これは、右隣の数字よりも小さい右端の数字です。由来
1234675
^
同じ桁の次に大きい数字は
1234756
見つかった数字は最後の数字（考慮された数字の最小）と交換され、残りの数字は昇順で配置されます。
数字を取り、それを数字に分割します。したがって、5桁の数字がある場合、5桁になります：abcde
ここで、dとeを入れ替えて、元の数値と比較します。それが大きい場合は、答えが得られます。
大きくない場合は、eとcを入れ替えます。ここで比較し、スワップdとeが小さい場合（再帰に注意）、最小にします。
数字が大きくなるまで続けてください。再帰を使用すると、約9行のスキームまたは20行のc＃として機能するはずです。
それは非常に興味深い質問です。
これが私のJavaバージョンです。他の寄稿者のコメントを確認する前に、パターンを理解してコードを完全に完成させるまでに約3時間かかります。私の考えが他の人とまったく同じであるのを見てうれしいです。
O（n）ソリューション。正直なところ、時間が15分しかなく、ホワイトボードで完全なコード仕上げが必要な場合は、このインタビューに失敗します。
これが私のソリューションにとって興味深いいくつかのポイントです。
コードに詳細なコメントを入れ、各ステップにBigOを入れました。
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);
orgNumbersList.add(nInt);
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;
}
Intelljで実行された結果は次のとおりです。
959879532-->959892357
1358642-->1362458
1234567-->1234576
77654321-->77654321
38276-->38627
47-->74
@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;
};
PHPコード
function NextHigherNumber($num1){
$num = strval($num1);
$max = 0;
for($i=(strlen($num)-2); $i>=0; $i--){
$numArrayRaw = substr($num, $i);
$numArray = str_split($numArrayRaw);
$max = max($numArray);
if ($numArray[0] < $max){
sort( $numArray, SORT_NUMERIC );
array_pop($numArray);
$numarrstr = implode("",$numArray);
$rt = substr($num,0,$i) . $max . $numarrstr;
return $rt;
}
}
return "-1";
}
echo NextHigherNumber(123);
（Javaでの）解決策は次のようになります（ここの友達はもっと良いものを見つけることができると確信しています）：
より大きな数字が得られるまで、文字列の末尾から数字の交換を開始します。
つまり、最初に下の桁を上に移動し始め、次に上の桁に到達するまで次の上の桁などに移動します。
次に、残りを並べ替えます。あなたの例では、次のようになります。
38276 --> 38267 (smaller) --> 38627 Found it
^ ^ ^
public static int nextDigit(int number){
String num = String.valueOf(number);
int stop = 0;
char [] chars = null;
outer:
for(int i = num.length() - 1; i > 0; i--){
chars = num.toCharArray();
for(int j = i; j > 0; j--){
char temp = chars[j];
chars[j] = chars[j - 1];
chars[j - 1] = temp;
if(Integer.valueOf(new String(chars)) > number){
stop = j;
break outer;
}
}
}
Arrays.sort(chars, stop, chars.length);
return Integer.valueOf(new String(chars));
}
C ++でプログラミングしている場合は、次を使用できますnext_permutation。
#include <algorithm>
#include <string>
#include <iostream>
int main(int argc, char **argv) {
using namespace std;
string x;
while (cin >> x) {
cout << x << " -> ";
next_permutation(x.begin(),x.end());
cout << x << "\n";
}
return 0;
}
この質問に答えるとき、私はブルートフォースアルゴリズムについて何も知らなかったので、別の角度からアプローチしました。number_given + 1から利用可能な最大数（3桁の数の場合は999、4桁の場合は9999など）まで、この数を再配置できる可能性のあるすべての解決策を検索することにしました。私は、各ソリューションの番号を並べ替えて、パラメーターとして指定された並べ替えられた番号と比較することにより、単語で回文を見つけるようなものを行いました。次に、ソリューションの配列の最初のソリューションを返しました。これが次の可能な値になるためです。
これがRubyの私のコードです：
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
end
私はこれを2つの数字でテストしただけです。彼らが働いていました。昨年12月に引退するまでの8年間、ITマネージャーとして、私は次の3つのことに気を配りました。2）速度：ユーザーが許容できる速度である必要があります。3）明快さ：私はおそらくあなたほど頭が良くないでしょうが、私はあなたにお金を払っています。自分がしていることを英語で説明してください。
オマール、これからも頑張ってください。
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
これを行う方法の優れた記述については、Knuthの「 TheArt of Computer Programming：Generating all Permutations」（。ps.gz）の「 AlgorithmL 」を参照してください。
これが私のコードです、これはこの例の修正版です
としょうかん：
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);
perm.add(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);
perm.add(new String(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);
}
指定されたn桁の数字に9を追加します。次に、制限内（最初の（n + 1）桁の数字）内にあるかどうかを確認します。その場合は、新しい番号の数字が元の番号の数字と同じであるかどうかを確認します。両方の条件が真になるまで、9を追加します。数が制限を超えたら、アルゴを停止します。
この方法の矛盾するテストケースを思い付くことができませんでした。
#include<stdio.h>
#include<cstring>
#include<iostream>
#include<string.h>
#include<sstream>
#include<iostream>
using namespace std;
int compare (const void * a, const void * b)
{
return *(char*)a-*(char*)b;
}
/*-----------------------------------------------*/
int main()
{
char number[200],temp;
cout<<"please enter your number?"<<endl;
gets(number);
int n=strlen(number),length;
length=n;
while(--n>0)
{
if(number[n-1]<number[n])
{
for(int i=length-1;i>=n;i--)
{
if(number[i]>number[n-1])
{
temp=number[i];
number[i]=number[n-1];
number[n-1]=temp;
break;
}
}
qsort(number+n,length-n,sizeof(char),compare);
puts(number);
return 0;
}
}
cout<<"sorry itz the greatest one :)"<<endl;
}
Pythonを使用した別の解決策：
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
public static void findNext(long number){
/* convert long to string builder */
StringBuilder s = new StringBuilder();
s.append(number);
int N = s.length();
int index=-1,pivot=-1;
/* from tens position find the number (called pivot) less than the number in right */
for(int i=N-2;i>=0;i--){
int a = s.charAt(i)-'0';
int b = s.charAt(i+1)-'0';
if(a<b){
pivot = a;
index =i;
break;
}
}
/* if no such pivot then no solution */
if(pivot==-1) System.out.println(" No such number ")
else{
/* find the minimum highest number to the right higher than the pivot */
int nextHighest=Integer.MAX_VALUE, swapIndex=-1;
for(int i=index+1;i<N;i++){
int a = s.charAt(i)-'0';
if(a>pivot && a<nextHighest){
nextHighest = a;
swapIndex=i;
}
}
/* swap the pivot and next highest number */
s.replace(index,index+1,""+nextHighest);
s.replace(swapIndex,swapIndex+1,""+pivot);
/* sort everything to right of pivot and replace the sorted answer to right of pivot */
char [] sort = s.substring(index+1).toCharArray();
Arrays.sort(sort);
s.replace(index+1,N,String.copyValueOf(sort));
System.out.println("next highest number is "+s);
}
}
以下は、数値のすべての順列を生成するコードです。ただし、最初にString.valueOf（integer）を使用してその整数を文字列に変換する必要があります。
/**
*
* 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) {
permutations.add(number);
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++) {
permutations.add(insertToNumberStringAtPosition(subPerm, dig,
inserterDig));
}
}
return permutations;
}
#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;
}
これがRubyでの私の実装です：
def foo num
num = num.to_s.chars.map(&:to_i)
return num.join.to_i if num.size < 2
for left in (num.size-2).downto(0) do
for right in (num.size-1).downto(left+1) do
if num[right]>num[left]
num[left],num[right] = num[right],num[left]
return (num[0..left] + num[left+1..num.size-1].sort).join.to_i
end
end
end
return num.join.to_i
end
p foo 38276
#will print: 38627
さらに別のJava実装で、箱から出してすぐに実行でき、テストで完了します。このソリューションは、古き良き動的計画法を使用したO（n）空間と時間です。
ブルートフォース攻撃を行う場合、ブルートフォースには2種類あります。
すべてのものを並べ替えてから、1分上を選択します：O（n！）
この実装と似ていますが、DPの代わりに、indexToIndexOfNextSmallerLeftマップにデータを入力するステップをbruteforcingしてO（n ^ 2）で実行します。
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import org.junit.Test;
import static org.junit.Assert.assertEquals;
public class NextHigherSameDigits {
public long next(final long num) {
final char[] chars = String.valueOf(num).toCharArray();
final int[] digits = new int[chars.length];
for (int i = 0; i < chars.length; i++) {
digits[i] = Character.getNumericValue(chars[i]);
}
final Map<Integer, Integer> indexToIndexOfNextSmallerLeft = new HashMap<>();
indexToIndexOfNextSmallerLeft.put(1, digits[1] > digits[0] ? 0 : null);
for (int i = 2; i < digits.length; i++) {
final int left = digits[i - 1];
final int current = digits[i];
Integer indexOfNextSmallerLeft = null;
if (current > left) {
indexOfNextSmallerLeft = i - 1;
} else {
final Integer indexOfnextSmallerLeftOfLeft = indexToIndexOfNextSmallerLeft.get(i - 1);
final Integer nextSmallerLeftOfLeft = indexOfnextSmallerLeftOfLeft == null ? null :
digits[indexOfnextSmallerLeftOfLeft];
if (nextSmallerLeftOfLeft != null && current > nextSmallerLeftOfLeft) {
indexOfNextSmallerLeft = indexOfnextSmallerLeftOfLeft;
} else {
indexOfNextSmallerLeft = null;
}
}
indexToIndexOfNextSmallerLeft.put(i, indexOfNextSmallerLeft);
}
Integer maxOfindexOfNextSmallerLeft = null;
Integer indexOfMinToSwapWithNextSmallerLeft = null;
for (int i = digits.length - 1; i >= 1; i--) {
final Integer indexOfNextSmallerLeft = indexToIndexOfNextSmallerLeft.get(i);
if (maxOfindexOfNextSmallerLeft == null ||
(indexOfNextSmallerLeft != null && indexOfNextSmallerLeft > maxOfindexOfNextSmallerLeft)) {
maxOfindexOfNextSmallerLeft = indexOfNextSmallerLeft;
if (maxOfindexOfNextSmallerLeft != null && (indexOfMinToSwapWithNextSmallerLeft == null ||
digits[i] < digits[indexOfMinToSwapWithNextSmallerLeft])) {
indexOfMinToSwapWithNextSmallerLeft = i;
}
}
}
if (maxOfindexOfNextSmallerLeft == null) {
return -1;
} else {
swap(digits, indexOfMinToSwapWithNextSmallerLeft, maxOfindexOfNextSmallerLeft);
reverseRemainingOfArray(digits, maxOfindexOfNextSmallerLeft + 1);
return backToLong(digits);
}
}
private void reverseRemainingOfArray(final int[] digits, final int startIndex) {
final int[] tail = Arrays.copyOfRange(digits, startIndex, digits.length);
for (int i = tail.length - 1; i >= 0; i--) {
digits[(digits.length - 1) - i] = tail[i];
}
}
private void swap(final int[] digits, final int currentIndex, final int indexOfNextSmallerLeft) {
int temp = digits[currentIndex];
digits[currentIndex] = digits[indexOfNextSmallerLeft];
digits[indexOfNextSmallerLeft] = temp;
}
private long backToLong(int[] digits) {
StringBuilder sb = new StringBuilder();
for (long i : digits) {
sb.append(String.valueOf(i));
}
return Long.parseLong(sb.toString());
}
@Test
public void test() {
final long input1 = 34722641;
final long expected1 = 34724126;
final long output1 = new NextHigherSameDigits().next(input1);
assertEquals(expected1, output1);
final long input2 = 38276;
final long expected2 = 38627;
final long output2 = new NextHigherSameDigits().next(input2);
assertEquals(expected2, output2);
final long input3 = 54321;
final long expected3 = -1;
final long output3 = new NextHigherSameDigits().next(input3);
assertEquals(expected3, output3);
final long input4 = 123456784987654321L;
final long expected4 = 123456785123446789L;
final long output4 = new NextHigherSameDigits().next(input4);
assertEquals(expected4, output4);
final long input5 = 9999;
final long expected5 = -1;
final long output5 = new NextHigherSameDigits().next(input5);
assertEquals(expected5, output5);
}
}
右端のビット0の後に1を見つけて、この右端の0ビットを1に反転する必要があります。
たとえば、入力が487で、バイナリでは111100111であるとします。
右端の0を反転し、その後に1が続きます
したがって、111101111を取得します
しかし、これで1が1つ減り、0が1つ減ったので、フリップビットの右側の1の数を1減らし、0ビットの数を1増やします。
111101011-バイナリ491
int getNextNumber(int input)
{
int flipPosition=0;
int trailingZeros=0;
int trailingOnes=0;
int copy = input;
//count trailing zeros
while(copy != 0 && (copy&1) == 0 )
{
++trailingZeros;
//test next bit
copy = copy >> 1;
}
//count trailing ones
while(copy != 0 && (copy&1) == 1 )
{
++trailingOnes;
//test next bit
copy = copy >> 1;
}
//if we have no 1's (i.e input is 0) we cannot form another pattern with
//the same number of 1's which will increment the input, or if we have leading consecutive
//ones followed by consecutive 0's up to the maximum bit size of a int
//we cannot increase the input whilst preserving the original no of 0's and
//1's in the bit pattern
if(trailingZeros + trailingOnes == 0 || trailingZeros + trailingOnes == 31)
return -1;
//flip first 0 followed by a 1 found from the right of the bit pattern
flipPosition = trailingZeros + trailingOnes+1;
input |= 1<<(trailingZeros+trailingOnes);
//clear fields to the right of the flip position
int mask = ~0 << (trailingZeros+trailingOnes);
input &= mask;
//insert a bit pattern to the right of the flip position that will contain
//one less 1 to compensate for the bit we switched from 0 to 1
int insert = flipPosition-1;
input |= insert;
return input;
}
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");
}
これがJavaの実装です
public static int nextHigherNumber(int number) {
Integer[] array = convertToArray(number);
int pivotIndex = pivotMaxIndex(array);
int digitInFirstSequence = pivotIndex -1;
int lowerDigitIndexInSecondSequence = lowerDigitIndex(array[digitInFirstSequence], array, pivotIndex);
swap(array, digitInFirstSequence, lowerDigitIndexInSecondSequence);
doRercursiveQuickSort(array, pivotIndex, array.length - 1);
return arrayToInteger(array);
}
public static Integer[] convertToArray(int number) {
int i = 0;
int length = (int) Math.log10(number);
int divisor = (int) Math.pow(10, length);
Integer temp[] = new Integer[length + 1];
while (number != 0) {
temp[i] = number / divisor;
if (i < length) {
++i;
}
number = number % divisor;
if (i != 0) {
divisor = divisor / 10;
}
}
return temp;
}
private static int pivotMaxIndex(Integer[] array) {
int index = array.length - 1;
while(index > 0) {
if (array[index-1] < array[index]) {
break;
}
index--;
}
return index;
}
private static int lowerDigitIndex(int number, Integer[] array, int fromIndex) {
int lowerMaxIndex = fromIndex;
int lowerMax = array[lowerMaxIndex];
while (fromIndex < array.length - 1) {
if (array[fromIndex]> number && lowerMax > array[fromIndex]) {
lowerMaxIndex = fromIndex;
}
fromIndex ++;
}
return lowerMaxIndex;
}
public static int arrayToInteger(Integer[] array) {
int number = 0;
for (int i = 0; i < array.length; i++) {
number+=array[i] * Math.pow(10, array.length-1-i);
}
return number;
}
これがユニットテストです
@Test
public void nextHigherNumberTest() {
assertThat(ArrayUtils.nextHigherNumber(34722641), is(34724126));
assertThat(ArrayUtils.nextHigherNumber(123), is(132));
}
これは非常に古い質問ですが、それでもc＃で簡単なコードを見つけることができませんでした。これは、インタビューに参加している人に役立つかもしれません。
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));
Console.ReadKey();
}
public static int[] GetIntArray(int num)
{
IList<int> listOfInts = new List<int>();
while (num > 0)
{
listOfInts.Add(num % 10);
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;
}
}
Javascriptを使用した非常に単純な実装、同じ数字で次に大きい数字
/*
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);
コメントがたくさんあるので、テキストエディタにコピーしたほうがいいです。ありがとう！
良い答えはたくさんありますが、まともなJava実装は見つかりませんでした。これが私の2セントです：
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;
}
これは、これよりもこのアルゴリズムに対するJavaのよりコンパクトな答えです。
public static int permutate2(int number){
String[] numArray = String.valueOf(number).split("");
for(int i = numArray.length - 1; i > 0; i--){
int current = Integer.valueOf(numArray[i]);
int previous = Integer.valueOf(numArray[i - 1]);
if(previous < current){
String[] rest = String.valueOf(number).substring(i, numArray.length).split("");
Arrays.sort(rest);
String picker = rest[0];
int pickerIndex = 0;
for(int n = 0; n < rest.length ; n++){
if(Integer.valueOf(rest[n]) > previous){
picker = rest[n];
pickerIndex = n;
break;
}
}
numArray[i - 1] = picker;
rest[pickerIndex] = String.valueOf(previous);
Arrays.sort(rest);
String newNumber = "";
for(int z = 0; z <= i - 1; z++){
newNumber += numArray[z];
}
for(String z : rest){
newNumber += z;
}
return Integer.valueOf(newNumber);
}
}
return number;
}
これが私がC＃で思いつかなかった賢い解決策です
using System;
using System.Linq;
public static long NextBiggerNumber(long n)
{
String str = GetNumbers(n);
for (long i = n+1; i <= long.Parse(str); i++)
{
if(GetNumbers(n)==GetNumbers(i))
{
return i;
}
}
return -1;
}
public static string GetNumbers(long number)
{
return string.Join("", number.ToString().ToCharArray().OrderByDescending(x => x));
}
Rubyソリューション
def next_bigger(num)
char_array = num.to_s.split('')
return -1 if char_array.uniq.size == 1
arr, target_idx, target_char = [], nil, nil
# get first left-digit less than the right from right side
(char_array.count - 1).times do |i|
arr.unshift(char_array[-(i+1)])
if char_array[-(i+2)] < char_array[-(i+1)]
target_idx = char_array.count - (i + 2)
target_char = char_array[-(i+2)]
arr.unshift(char_array[-(i+2)])
break
end
end
return -1 unless target_idx
# first smallest digit larger than target_char to the right
((target_char.to_i + 1)..9).to_a.each do |ch|
if arr.index(ch.to_s)
flip_char = arr.delete_at(arr.index(ch.to_s))
# sort the digits to the right of flip_char
arr.sort!
# place flip_char to the left of target_char
arr.unshift(flip_char)
break
end
end
(char_array[0...target_idx] + arr).join().to_i
end
PHPでの実装
時間計算量O（n）
$n = "9875";
$n_size = strlen($n);
for($i = $n_size-1; $i > 0; $i-- ) {
if($n[$i] > $n[$i-1]){
$temp = $n[$i];
$n[$i] = $n[$i-1];
$n[$i-1] = $temp;
break;
}
}
if($i == 0){
echo "Next Greater value no possible";
}else{
echo $n;
}
private static int GetNextHigherNumber(int num)
{
//given 38276 return 38627
string numberstring = num.ToString();
char[] sNum = numberstring.ToCharArray();
for (int i = sNum.Length - 1; i > 0; i--)
{
for (int j = i - 1; j > 0; j--)
{
if (sNum[i] > sNum[j])
{
for (int x = i; x > j; x--)
{
char chr = sNum[x];
sNum[x] = sNum[x - 1];
sNum[x - 1] = chr;
}
i = 0;
break;
}
}
}
numberstring = string.Empty;
for(int x= 0 ; x<sNum.Length;x++)
{
numberstring += sNum[x].ToString();
}
return Convert.ToInt32(numberstring);
}
もう1つの条件を追加したJavaでの回答
次の番号も偶数である必要があります
public static int nextDigit(int number) {
String num = String.valueOf(number);
int stop = 0;
char[] orig_chars = null;
char[] part1 = null;
char[] part2 = null;
orig_chars = num.toCharArray();
System.out.println("vivek c r");
for (int i = orig_chars.length - 1; i > 0; i--) {
String previous = orig_chars[i - 1] + "";
String next = orig_chars[i] + "";
if (Integer.parseInt(previous) < Integer.parseInt(next))
{
if (Integer.parseInt(previous) % 2 == 0) {
String partString1 = "";
String partString2 = "";
for (int j = 0; j <= i - 1; j++) {
partString1 = partString1.concat(orig_chars[j] + "");
}
part1 = partString1.toCharArray();
for (int k = i; k < orig_chars.length; k++) {
partString2 = partString2.concat(orig_chars[k] + "");
}
part2 = partString2.toCharArray();
Arrays.sort(part2);
for (int l = 0; l < part2.length; l++) {
char temp = '0';
if (part2[l] > part1[i - 1]) {
temp = part1[i - 1];
part1[i - 1] = part2[l];
part2[l] = temp;
break;
}
}
for (int m = 0; m < part2.length; m++) {
char replace = '0';
if (part2[m] % 2 == 0) {
replace = part2[m];
for (int n = m; n < part2.length - 1; n++) {
part2[n] = part2[n + 1];
}
part2[part2.length - 1] = replace;
break;
}
}
System.out.print(part1);
System.out.println(part2);
System.exit(0);
}
}
}
System.out.println("NONE");
return 0;
}
#include <iostream>
using namespace std;
int main ()
{
int num=15432;
int quot,rem;
int numarr[5];
int length=0;
while(num!=0)
{
rem=num%10;
num = num/10;
numarr[length]=rem;
length++;
}
for(int j=0;j<length;j++)
{
for(int i=0;i<length;i++)
{
if(numarr[i]<numarr[i+1])
{
int tmp=numarr[i];
numarr[i]=numarr[i+1];
numarr[i+1]=tmp;
}
}
}
for(int j=0;j<length;j++)
{
cout<<numarr[j];
}
return 0;
}
import java.util.Scanner;
public class Big {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.print("Enter the number ");
String str = sc.next();
int t=0;
char[] chars = str.toCharArray();
for(int i=str.length()-1,j=str.length()-2;j>=0;j--)
{
if((int)chars[i]>(int)chars[j])
{
t = (int)chars[i];
chars[i] = chars[j];
chars[j]=(char)t;
for(int k=j+1;k<str.length()-1;k++)
{
for(int l=k+1;l<str.length();l++)
{
if(chars[k]>chars[l])
{
int m = (int)chars[k];
chars[k] = chars[l];
chars[l]=(char)m;
}
}
}
break;
}
}
System.out.print("The next Big number is: ");
for(int i=0;i<str.length();i++){
System.out.print(chars[i]);
}
sc.close();
}
}