Рубрики

Найти следующее большее число с таким же набором цифр

Учитывая число n, найдите наименьшее число, которое имеет тот же набор цифр, что и n, и больше, чем n. Если n — максимально возможное число с его набором цифр, выведите «не возможно».

Примеры:
Для простоты реализации мы рассмотрели входной номер в виде строки.

Input:  n = "218765"
Output: "251678"

Input:  n = "1234"
Output: "1243"

Input: n = "4321"
Output: "Not Possible"

Input: n = "534976"
Output: "536479"

Ниже приведены несколько замечаний по поводу следующего большего числа.
1) Если все цифры отсортированы в порядке убывания, то вывод всегда «Не возможно». Например, 4321.
2) Если все цифры отсортированы в порядке возрастания, то нам нужно поменять местами последние две цифры. Например, 1234.
3) В других случаях нам нужно обработать число с правой стороны (почему? Потому что нам нужно найти наименьшее из всех больших чисел)

Теперь вы можете попробовать разработать алгоритм самостоятельно.

Ниже приведен алгоритм поиска следующего большего числа.
I) Пройдите заданное число от крайней правой цифры, продолжайте движение, пока не найдете цифру, которая меньше, чем ранее пройденная цифра. Например, если введено число «534976», мы останавливаемся на 4, потому что 4 меньше следующей цифры 9. Если мы не найдем такую цифру, то вывод «Не возможно».

II) Теперь найдите правую часть найденной цифры «d», чтобы найти наименьшую цифру, превышающую «d». Для «53 4 976» правая часть 4 содержит «976». Наименьшая цифра больше 4 — 6 .

III) Поменяйте местами найденные выше две цифры, мы получим 53 6 97 4 в приведенном выше примере.

IV) Теперь отсортируйте все цифры от позиции рядом с 'd' до конца числа. Число, которое мы получаем после сортировки, является выходным. Для приведенного выше примера мы сортируем цифры жирным шрифтом 536 974 . Мы получаем «536 479 », который является следующим большим числом для ввода 534976.

Ниже приводится реализация вышеуказанного подхода.

С

// C ++ программа для поиска наименьшего числа, которое больше заданного числа
// и имеет тот же набор цифр, что и данный номер
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

  
// Утилита для замены двух цифр

void swap(char *a, char *b)

{

    char temp = *a;

    *a = *b;

    *b = temp;

}

  
// Учитывая число как номер массива char [], эта функция находит
// следующее большее число. Он изменяет тот же массив, чтобы сохранить результат

void findNext(char number[], int n)

{

    int i, j;

  

    // I) Начинаем с самой правой цифры и находим первую цифру, которая

    // меньше цифры рядом с ней.

    for (i = n-1; i > 0; i--)

        if (number[i] > number[i-1])

           break;

  

    // Если такой цифры не найдено, то все цифры в порядке убывания

    // означает, что не может быть большего числа с таким же набором цифр

    if (i==0)

    {

        cout << "Next number is not possible";

        return;

    }

  

    // II) Найти наименьшую цифру в правой части (i-1) '-ой цифры, которая

    // больше чем число [i-1]

    int x = number[i-1], smallest = i;

    for (j = i+1; j < n; j++)

        if (number[j] > x && number[j] < number[smallest])

            smallest = j;

  

    // III) Поменяйте местами найденную наименьшую цифру с номером [i-1]

    swap(&number[smallest], &number[i-1]);

  

    // IV) Сортировка цифр после (i-1) в порядке возрастания

    sort(number + i, number + n);

  

    cout << "Next number with same set of digits is " << number;

  

    return;

}

  
// Программа драйвера для проверки вышеуказанной функции

int main()

{

    char digits[] = "534976";

    int n = strlen(digits);

    findNext(digits, n);

    return 0;

}

Джава

// Java программа для поиска следующего большего
// номер с таким же набором цифр.

import java.util.Arrays;

  

public class nextGreater 

{

    // Утилита для замены двух цифр

    static void swap(char ar[], int i, int j) 

    {

        char temp = ar[i];

        ar[i] = ar[j];

        ar[j] = temp;

    }

  

    // Задано число как номер массива char [],

    // эта функция находит следующее большее число.

    // Он изменяет тот же массив, чтобы сохранить результат

    static void findNext(char ar[], int n) 

    {

        int i;

          

        // I) Начинаем с самой правой цифры

        // и найти первую цифру, которая меньше

        // чем цифра рядом с ним.

        for (i = n - 1; i > 0; i--) 

        {

            if (ar[i] > ar[i - 1]) {

                break;

            }

        }

          

        // Если такой цифры не найдено, то все

        // цифры в порядке убывания

        // не может быть большего числа с

        // тот же набор цифр

        if (i == 0

        {

            System.out.println("Not possible");

        

        else 

        {

            int x = ar[i - 1], min = i;

              

            // II) Найдите самую маленькую цифру справа

            // сторона (i-1) '-ой цифры, которая больше

            // чем число [i-1]

            for (int j = i + 1; j < n; j++) 

            {

                if (ar[j] > x && ar[j] < ar[min]) 

                {

                    min = j;

                }

            }

  

            // III) поменяйте местами найденное самое маленькое

            // цифра с номером [i-1]

            swap(ar, i - 1, min);

  

            // IV) Сортировать цифры после (i-1)

            // в порядке возрастания

            Arrays.sort(ar, i, n);

            System.out.print("Next number with same" +

                                    " set of digits is ");

            for (i = 0; i < n; i++)

                System.out.print(ar[i]);

        }

    }

  

    public static void main(String[] args) 

    {

        char digits[] = { '5','3','4','9','7','6' };

        int n = digits.length;

        findNext(digits, n);

    }

}

питон

# Программа Python, чтобы найти наименьшее число, которое
# больше заданного нет. имеет такой же набор
# цифры как заданный номер

  
# Заданный номер в виде массива int, эта функция находит
# наибольшее число и возвращает число в виде целого числа

def findNext(number,n):

       

     # Начните с самой правой цифры и найдите первую

     # цифра меньше цифры рядом с ней

     for i in range(n-1,0,-1):

         if number[i] > number[i-1]:

             break

               

     # Если такая цифра не найдена, то все цифры находятся в

     # по убыванию, большее число невозможно

     if i == 0:

         print "Next number not possible"

         return

           

     # Найдите самую маленькую цифру на правой стороне

     # (i-1) ая цифра, которая больше, чем число [i-1]

     x = number[i-1]

     smallest = i

     for j in range(i+1,n):

         if number[j] > x and number[j] < number[smallest]:

             smallest = j

           

     # Поменять местами найденную наименьшую цифру с (i-1) 'th

     number[smallest],number[i-1] = number[i-1], number[smallest]

       

     # X - конечное число в виде целочисленного типа

     x = 0

     # Преобразование списка до i-1 в число

     for j in range(i):

         x = x * 10 + number[j]

       

     # Сортировать цифры после i-1 в порядке возрастания

     number = sorted(number[i:])

     # преобразование оставшихся отсортированных цифр в число

     for j in range(n-i):

         x = x * 10 + number[j]

       

     print "Next number with set of digits is",x

  

  
Программа # Driver для проверки вышеуказанной функции

digits = "534976"         

  
# преобразование в целочисленный массив,
№ становится [5,3,4,9,7,6]

number = map(int ,digits) 

findNext(number, len(digits))

  
# Этот код предоставлен Harshit Agrawal

C #

// C # программа для поиска следующего большего
// номер с таким же набором цифр.

using System;

                      

public class nextGreater 

{

    // Утилита для замены двух цифр

    static void swap(char []ar, int i, int j) 

    {

        char temp = ar[i];

        ar[i] = ar[j];

        ar[j] = temp;

    }

  

    // Задано число как номер массива char [],

    // эта функция находит следующее большее число.

    // Он изменяет тот же массив, чтобы сохранить результат

    static void findNext(char []ar, int n) 

    {

        int i;

          

        // I) Начинаем с самой правой цифры

        // и найти первую цифру, которая меньше

        // чем цифра рядом с ним.

        for (i = n - 1; i > 0; i--) 

        {

            if (ar[i] > ar[i - 1]) 

            {

                break;

            }

        }

          

        // Если такой цифры не найдено, то все

        // цифры в порядке убывания

        // не может быть большего числа с

        // тот же набор цифр

        if (i == 0) 

        {

            Console.WriteLine("Not possible");

        

        else

        {

            int x = ar[i - 1], min = i;

              

            // II) Найдите самую маленькую цифру справа

            // сторона (i-1) '-ой цифры, которая больше

            // чем число [i-1]

            for (int j = i + 1; j < n; j++) 

            {

                if (ar[j] > x && ar[j] < ar[min]) 

                {

                    min = j;

                }

            }

  

            // III) поменяйте местами найденное самое маленькое

            // цифра с номером [i-1]

            swap(ar, i - 1, min);

  

            // IV) Сортировать цифры после (i-1)

            // в порядке возрастания

            Array.Sort(ar, i, n-i);

            Console.Write("Next number with same" +

                                    " set of digits is ");

            for (i = 0; i < n; i++)

                Console.Write(ar[i]);

        }

    }

  

    // Код драйвера

    public static void Main(String[] args) 

    {

        char []digits = { '5','3','4','9','7','6' };

        int n = digits.Length;

        findNext(digits, n);

    }

}

  
// Этот код предоставлен 29AjayKumar


Выход:

Next number with same set of digits is 536479

Вышеуказанная реализация может быть оптимизирована следующими способами.
1) Мы можем использовать бинарный поиск на шаге II вместо линейного поиска.
2) На шаге IV вместо простой сортировки мы можем применить некоторую умную технику, чтобы сделать это за линейное время. Подсказка: мы знаем, что все цифры линейно отсортированы в обратном порядке, кроме одной цифры, которая была заменена.

С помощью приведенных выше оптимизаций мы можем сказать, что временная сложность этого метода составляет O (n).

Эта статья пополняемая Рахул Джейна. Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

Найти следующее большее число с таким же набором цифр

0.00 (0%) 0 votes