Рубрики

Построить наименьшее число, удалив n цифр из данного числа

Имея строку цифр 'str' и целое число 'n', постройте наименьшее возможное число, удалив из строки 'n' цифр и не меняя порядок ввода цифр.

Примеры:

Input: str = "4325043", n = 3
Output: "2043"

Input: str = "765028321", n = 5
Output: "0221"

Input: str = "121198", n = 2
Output: "1118" 

Идея основана на том факте, что символ из первых (n + 1) символов должен быть в результирующем числе. Таким образом, мы выбираем наименьшую из первых (n + 1) цифр и помещаем ее в результат, и повторяем для оставшихся символов. Ниже приведен полный алгоритм.

Initialize result as empty string
     res = ""
buildLowestNumber(str, n, res)
1) If n == 0, then there is nothing to remove.
   Append the whole 'str' to 'res' and return

2) Let 'len' be length of 'str'. If 'len' is smaller or equal 
   to n, then everything can be removed
   Append nothing to 'res' and return

3) Find the smallest character among first (n+1) characters
   of 'str'.  Let the index of smallest character be minIndex.
   Append 'str[minIndex]' to 'res' and recur for substring after
   minIndex and for n = n-minIndex

     buildLowestNumber(str[minIndex+1..len-1], n-minIndex).

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

C ++

// C ++ программа для построения наименьшего числа путем удаления n цифр из
// заданное число
#include<iostream>

using namespace std;

  
// Рекурсивная функция, которая удаляет n символов из str
// сохранить наименьшее возможное число в 'res'

void buildLowestNumberRec(string str, int n, string &res)

{

    // Если есть 0 символов для удаления из str,

    // добавляем все к результату

    if (n == 0)

    {

        res.append(str);

        return;

    }

  

    int len = str.length();

  

    // Если нужно удалить больше символов, чем строку

    // длина, затем ничего не добавляется к результату

    if (len <= n)

        return;

  

    // Находим наименьший символ среди первых (n + 1) символов

    // ул.

    int minIndex = 0;

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

        if (str[i] < str[minIndex])

            minIndex = i;

  

    // Добавляем наименьший символ к результату

    res.push_back(str[minIndex]);

  

    // подстрока, начинающаяся с minIndex + 1 до str.length () - 1.

    string new_str = str.substr(minIndex+1, len-minIndex);

  

    // Рекурс для вышеуказанной подстроки и n равно n-minIndex

    buildLowestNumberRec(new_str, n-minIndex, res);

}

  
// Оболочка над buildLowestNumberRec ()

string buildLowestNumber(string str, int n)

{

    string res = "";

  

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

    buildLowestNumberRec(str, n, res);

  

    return res;

}

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

int main()

{

    string str = "121198";

    int n = 2;

    cout << buildLowestNumber(str, n);

    return 0;

}

Джава

// Java программа для построения наименьшего числа
// удаляя n цифр из заданного номера

class GFG 

{

  

    // переменная класса используется, потому что Java

    // строго передаем по значению, чтобы "обертка не работала"

    // как res передается по ссылке

    static String res = "";

  

    // Рекурсивная функция, которая удаляет

    // 'n' символов из 'str' для хранения

    // наименьшее возможное число в 'res'

    static void buildLowestNumberRec(String str, int n) 

    {

  

        // Если есть 0 символов для удаления из str,

        // добавляем все к результату

        if (n == 0

        {

            res.concat(str);

            return;

        }

  

        int len = str.length();

  

        // Если есть еще символы

        // удалить длину строки,

        // затем ничего не добавляем к результату

        if (len <= n)

            return;

  

        // Находим самый маленький символ среди

        // первые (n + 1) символов str.

        int minIndex = 0;

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

            if (str.charAt(i) < str.charAt(minIndex))

                minIndex = i;

  

        // Добавляем наименьший символ к результату

        res += str.charAt(minIndex);

  

        // подстрока начиная с

        // minIndex + 1 до str.length () - 1.

        String new_str = str.substring(minIndex + 1);

  

        // повторить указанную подстроку

        // и n равно n-minIndex

        buildLowestNumberRec(new_str, n - minIndex);

    }

  

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

    public static void main(String[] args) 

    {

        String str = "121198";

        int n = 2;

        buildLowestNumberRec(str, n);

        System.out.println(res);

    }

}

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

C #

// C # программа для построения наименьшего числа
// удаляя n цифр из заданного номера

using System;

  

class GFG 

    static String res = ""

  

    // Рекурсивная функция, которая удаляет

    // 'n' символов из 'str' для хранения

    // наименьшее возможное число в 'res'

    static void buildLowestNumberRec(String str, 

                                          int n) 

    

  

        // Если есть 0 символов для удаления из str,

        // добавляем все к результату

        if (n == 0) 

        

            res += str; 

            return

        

  

        int len = str.Length; 

  

        // Если есть еще символы

        // удалить длину строки,

        // затем ничего не добавляем к результату

        if (len <= n) 

            return

  

        // Находим самый маленький символ среди

        // первые (n + 1) символов str.

        int minIndex = 0; 

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

            if (str[i] < str[minIndex]) 

                minIndex = i; 

  

        // Добавляем наименьший символ к результату

        res += str[minIndex]; 

  

        // подстрока начиная с

        // minIndex + 1 до str.length () - 1.

        String new_str = str.Substring(minIndex + 1); 

  

        // повторить указанную подстроку

        // и n равно n-minIndex

        buildLowestNumberRec(new_str, n - minIndex); 

    

  

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

    public static void Main(String[] args) 

    

        String str = "121198"

        int n = 2; 

        buildLowestNumberRec(str, n); 

        Console.Write(res); 

    

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

Выход:

1118

Ниже приведен оптимизированный код на C ++, предоставленный Gaurav Mamgain

// C ++ программа для построения наименьшего числа путем удаления
// n цифр из заданного числа
#include<bits/stdc++.h>

using namespace std;

  

void insertInNonDecOrder(deque<char> &dq, char ch)

{

    // если контейнер пуст, вставить текущую цифру

    if (dq.empty())

        dq.push_back(ch);

  

    else

    {

        char temp = dq.back();

  

        // Продолжаем удалять цифры больше текущей цифры

        // с обратной стороны deque

        while( temp > ch && !dq.empty())

        {

            dq.pop_back();

            if (!dq.empty())

                temp = dq.back();

        }

        dq.push_back(ch); // вставить текущую цифру

    }

    return;

}

  

string buildLowestNumber(string str, int n)

{

    int len = str.length();

  

    // удаление n цифр означает, что нам нужно напечатать k цифр

    int k = len - n;

  

    deque<char> dq;

    string res = "";

  

    // оставляя самые правые цифры k-1, которые нам нужно выбрать

    // минимальная цифра от остальной части строки и распечатка

    int i;

    for (i=0; i<=len-k; i++)

  

        // вставить новую цифру с обратной стороны в

        // соответствующая позиция и / продолжаем удаление

        // цифры больше текущей цифры

        insertInNonDecOrder(dq, str[i]);

  

    // Теперь минимальная цифра находится перед deque

    while (i < len)

    {

        // сохраняем минимальную цифру в выходной строке

        res += dq.front();

  

        // удаляем минимальную цифру

        dq.pop_front();

  

        // Снова вставляем новую цифру сзади

        // сторона в соответствующей позиции и удержание

        // удаляем цифры больше текущей цифры

        insertInNonDecOrder(dq, str[i]);

        i++;

    }

  

    // Теперь в деке будет только один элемент

    res += dq.front();

    dq.pop_front();

    return res;

}

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

int main()

{

    string str = "765028321";

    int n = 5;

    cout << buildLowestNumber(str, n)<< endl;

    return 0;

}
// Этот код предоставлен Gaurav Mamgain

Выход:

0221

Сложность времени: O (n)
Космическая сложность: O (n)

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

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

Построить наименьшее число, удалив n цифр из данного числа

0.00 (0%) 0 votes