algorithm - termino - Dado un número, encuentre el siguiente número más alto que tenga exactamente el mismo conjunto de dígitos que el número original
termino enesimo de una sucesion ejercicios resueltos (30)
A continuación se muestra el código para generar todas las permutaciones de un número ... aunque uno tiene que convertir ese entero en una cadena usando String.valueOf (integer) primero.
/**
*
* 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;
}
Acabo de bombardear una entrevista e hice casi cero progresos en mi pregunta de la entrevista. ¿Alguien puede decirme cómo hacer esto? Intenté buscar en línea pero no pude encontrar nada:
Dado un número, encuentre el siguiente número más alto que tenga exactamente el mismo conjunto de dígitos que el número original. Por ejemplo: dado 38276 retorno 38627
Quería comenzar encontrando el índice del primer dígito (de la derecha) que era menor que el dígito de las unidades. Luego rotaría los últimos dígitos del subconjunto de modo que fuera el siguiente número más grande compuesto por los mismos dígitos, pero se atascara.
El entrevistador también sugirió tratar de intercambiar los dígitos uno a la vez, pero no pude averiguar el algoritmo y solo observé una pantalla durante unos 20-30 minutos. No hace falta decir que creo que voy a tener que continuar la búsqueda de empleo.
Edición: por lo que vale la pena, me invitaron a la siguiente ronda de entrevistas.
Aquí está mi código, es una versión modificada de este ejemplo.
Biblioteca:
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;
}
}
Prueba:
public static void main(String[] args)
{
int a = 38276;
int b = NumPermExample.nextPermutation(a);
System.out.println("a: "+a+", b: "+b);
}
Aquí está mi implementación en 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
puedes leer mas here
Aquí hay una solución compacta (pero en parte fuerza bruta) en Python
def findnext(ii): return min(v for v in (int("".join(x)) for x in
itertools.permutations(str(ii))) if v>ii)
En C ++ puede hacer las permutaciones de esta manera: https://.com/a/9243091/1149664 (es el mismo algoritmo que el de itertools)
Aquí hay una implementación de la respuesta principal descrita por Weeble y BlueRaja, (otras respuestas). Dudo que haya algo mejor.
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)))))
Como mínimo, aquí hay un par de ejemplos de soluciones basadas en la fuerza bruta, que debería haber podido encontrar desde la parte superior de su cabeza:
La lista de dígitos en 38276 ordenada es 23678
La lista de dígitos en 38627 ordenada es 23678
fuerza bruta incrementa, ordena y compara
A lo largo de la fuerza bruta, las soluciones se convertirían en una cadena y la fuerza bruta todos los números posibles usando esos dígitos.
Cree ints de todos ellos, póngalos en una lista y ordénelos, obtenga la siguiente entrada después de la entrada de destino.
Si pasara 30 minutos en esto y al menos no lograra al menos un enfoque de fuerza bruta, tampoco lo contrataría.
En el mundo de los negocios, una solución que no sea elegante, lenta y torpe pero que haga el trabajo es siempre más valiosa que ninguna solución, de hecho, que describe prácticamente todo el software empresarial, poco elegante, lento y torpe.
Esa es una pregunta muy interesante.
Aquí está mi versión de java. Tómeme alrededor de 3 horas a partir de averiguar el patrón para terminar completamente el código antes de revisar los comentarios de otros colaboradores. Me alegra ver que mi idea es muy parecida a la de otros.
O (n) solución. Honestamente, fallaré en esta entrevista si el tiempo es de solo 15 minutos y requerirá el final del código completo en la pizarra.
Aquí hay algunos puntos de interés para mi solución:
- Evita cualquier clasificación.
- Evita completamente la operación de cuerdas
- Lograr la complejidad del espacio O (logN)
Pongo comentarios detallados en mi código, y el Big O en cada paso.
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;
}
Aquí está el resultado que se ejecuta en Intellj:
959879532-->959892357
1358642-->1362458
1234567-->1234576
77654321-->77654321
38276-->38627
47-->74
Estoy bastante seguro de que su entrevistador estaba tratando de empujarlo suavemente hacia algo como esto:
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);
No necesariamente la solución más eficiente o elegante, pero resuelve el ejemplo proporcionado en dos ciclos e intercambia dígitos uno a la vez, como sugirió.
No sabía nada sobre el algoritmo de fuerza bruta cuando respondía esta pregunta, así que lo abordé desde otro ángulo. Decidí buscar en la gama completa de soluciones posibles en las que este número podría reorganizarse, comenzando por number_given + 1 hasta el número máximo disponible (999 para un número de 3 dígitos, 9999 para 4 dígitos, etc.). Hice algo así como encontrar un palíndromo con palabras, ordenando los números de cada solución y comparándolo con el número ordenado dado como parámetro. Luego simplemente devolví la primera solución en el conjunto de soluciones, ya que este sería el siguiente valor posible.
Aquí está mi código en 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
fin
Otra implementación de Java, ejecutable fuera de la caja y completada con pruebas. Esta solución es O (n) espacio y tiempo utilizando una buena programación dinámica antigua.
Si uno quiere fuerza bruta, hay 2 tipos de fuerza bruta:
Permuta todas las cosas, luego elige min más alto: O (n!)
Similar a esta implementación, pero en lugar de DP, el proceso de rellenar el mapa indexToIndexOfNextSmallerLeft se ejecutará en 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);
}
}
Para una buena reseña de cómo hacer esto, vea " Algoritmo L " en " El arte de la programación de computadoras de Knuth : Generando todas las permutaciones " (.ps.gz).
Puede hacerlo en O(n) (donde n es el número de dígitos) de la siguiente manera:
A partir de la derecha, encontrará el primer par de dígitos de manera que el dígito de la izquierda sea más pequeño que el dígito de la derecha. Vamos a referirnos al dígito izquierdo por "dígito-x". Encuentre el número más pequeño más grande que digit-x a la derecha de digit-x, y colóquelo inmediatamente a la izquierda de digit-x. Finalmente, ordene los dígitos restantes en orden ascendente, ya que ya estaban en orden descendente , todo lo que necesita hacer es revertirlos (guarde para dígito-x, que se puede colocar en el lugar correcto en O(n) ) .
Un ejemplo lo hará más claro:
123456784987654321 start with a number 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''
Prueba de corrección:
Usemos letras mayúsculas para definir cadenas de dígitos y minúsculas para los dígitos. La sintaxis AB significa "la concatenación de las cadenas A y B " . < es el orden lexicográfico, que es lo mismo que el ordenamiento de enteros cuando las cadenas de dígitos tienen la misma longitud.
Nuestro número original N es de la forma AxB , donde x es un solo dígito y B se clasifica en forma descendente.
El número encontrado por nuestro algoritmo es AyC , donde y ∈ B es el dígito más pequeño > x (debe existir debido a la forma en que se seleccionó x , ver arriba) , y C se clasifica en forma ascendente.
Suponga que hay algún número (usando los mismos dígitos) N'' tal que AxB < N'' < AyC . N'' debe comenzar con A o, de lo contrario, no podría caer entre ellos, por lo que podemos escribirlo en el formato AzD . Ahora nuestra desigualdad es AxB < AzD < AyC , que es equivalente a xB < zD < yC donde las tres cadenas de dígitos contienen los mismos dígitos.
Para que eso sea cierto, debemos tener x <= z <= y . Dado que y es el dígito más pequeño > x , z no puede estar entre ellos, entonces z = x o z = y . Di z = x . Entonces nuestra desigualdad es xB < xD < yC , lo que significa B < D donde B y D tienen los mismos dígitos. Sin embargo, B se clasifica en forma descendente, por lo que no hay una cadena con esos dígitos más grandes que ella. Por lo tanto no podemos tener B < D . Siguiendo los mismos pasos, vemos que si z = y , no podemos tener D < C .
Por lo tanto, N'' no puede existir, lo que significa que nuestro algoritmo encuentra correctamente el siguiente número más grande.
Sólo he probado esto con dos números. Ellos trabajaron. Como Gerente de TI durante 8 años hasta que me jubilé en diciembre pasado, me importaron tres cosas: 1) Precisión: es bueno si funciona, siempre. 2) Velocidad: tiene que ser aceptable para el usuario. 3) Claridad: Probablemente no soy tan inteligente como tú, pero te pago. Asegúrate de explicar lo que estás haciendo, en inglés.
Omar, la mejor de las suertes.
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
Si está programando en C ++, puede usar 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;
}
Solo otra solución usando 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)
Salida:
23541
Suma 9 al número de n dígitos dado. Luego verifique si está dentro del límite (el primer número de dígitos (n + 1)). Si es así, compruebe si los dígitos en el nuevo número son los mismos que en el número original. Repita agregando 9 hasta que ambas condiciones sean verdaderas. Detener el algo cuando el número va más allá del límite.
No pude encontrar un caso de prueba contradictorio para este método.
Toma un número y divídelo en dígitos. Entonces, si tenemos un número de 5 dígitos, tenemos 5 dígitos: abcde
Ahora intercambie d y e y compare con el número original, si es más grande, tiene su respuesta.
Si no es más grande, cambia e y c. Ahora compare y si es más pequeño el cambio de d y e nuevamente (observe la recursión), tome el más pequeño.
Continúa hasta que encuentres un número más grande. Con la recursión debería funcionar como aproximadamente 9 líneas de esquema, o 20 de c #.
Tu idea
Quería comenzar encontrando el índice del primer dígito (de la derecha) que era menor que el dígito de las unidades. Luego rotaría los últimos dígitos del subconjunto de modo que fuera el siguiente número más grande compuesto por los mismos dígitos, pero se atascara.
es bastante bueno, en realidad Solo debe tener en cuenta no solo el último dígito sino todos los dígitos de menor significado que el considerado actualmente. Como antes de que se alcance eso, tenemos una secuencia monotónica de dígitos, que es el dígito más a la derecha más pequeño que su vecino derecho. Considerar
1234675
^
El siguiente número más grande con los mismos dígitos es
1234756
El dígito encontrado se intercambia por el último dígito, el más pequeño de los dígitos considerados, y los dígitos restantes se ordenan en orden creciente.
Un problema casi idéntico apareció como un problema de Code Jam y tiene una solución aquí:
http://code.google.com/codejam/contest/dashboard?c=186264#s=a&a=1
Aquí hay un resumen del método usando un ejemplo:
34722641
A. Divida la secuencia de dígitos en dos, de modo que la parte derecha sea lo más larga posible y permanezca en orden decreciente:
34722 641
(Si todo el número está en orden decreciente, no se puede hacer un número mayor sin agregar dígitos).
B.1. Seleccione el último dígito de la primera secuencia:
3472(2) 641
B.2. Encuentra el dígito más pequeño en la segunda secuencia que es más grande que él:
3472(2) 6(4)1
B.3. Intercambialas
3472(2) 6(4)1
->
3472(4) 6(2)1
->
34724 621
C. Ordenar la segunda secuencia en orden creciente:
34724 126
D. Hecho!
34724126
Una implementación javascript del algoritmo de @ BlueRaja.
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;
};
Una solución (en Java) podría ser la siguiente (estoy seguro de que los amigos aquí pueden encontrar una mejor):
Comience a intercambiar dígitos desde el final de la cadena hasta que obtenga un número más alto.
Es decir, primero comience a subir el dígito inferior. Luego, el siguiente más alto, etc., hasta que llegue al siguiente más alto.
Entonces ordena el resto. En tu ejemplo obtendrías:
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));
}
Implementación muy simple usando Javascript, el siguiente número más alto con los mismos dígitos
/*
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);
Ya que hay muchos comentarios, entonces es mejor que puedas copiarlo a tu editor de texto. ¡Gracias!
Aquí está la implementación de 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;
}
Aquí están las pruebas unitarias
@Test
public void nextHigherNumberTest() {
assertThat(ArrayUtils.nextHigherNumber(34722641), is(34724126));
assertThat(ArrayUtils.nextHigherNumber(123), is(132));
}
Hay muchas respuestas buenas, pero no encontré una implementación de Java decente. Aquí están mis dos centavos:
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;
}
Necesitamos encontrar el bit 0 más a la derecha seguido de un 1 y voltear este bit 0 más a la derecha.
por ejemplo, digamos que nuestra entrada es 487, que es 111100111 en binario.
Damos la vuelta a la derecha más 0 que tiene 1 siguiéndolo
así obtenemos 111101111
pero ahora tenemos un 1 extra y uno menos 0, por lo que reducimos el número de 1 a la derecha del bit de inversión en 1 y aumentamos el no de 0 bits en 1, lo que da como resultado
111101011 - binario 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;
}
Sé que esta es una pregunta muy antigua pero aún no encontré un código fácil en c #. Esto podría ayudar a los chicos que están asistiendo a las entrevistas.
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;
}
}
#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;
}
#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;
}
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");
}
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);
}
}