Implement the NextBiggerThan method which finds the nearest largest integer consisting of the digits of the given positive integer number and null if no such number exists.
Topics - loops, algorithms
C#
Как реализовать данный метод?
Очевидно, что для поиска такого числа необходимо:
1. Поменять местами первую идущую не в порядке возрастания цифру на минимальную из оставшихся бОльших цифр.
2. Отсортировать оставшиеся цифры.
Например, есть число 12085640
Нолик не идет по порядку - меняем его на 4:
12485600
А теперь сортируем:
12400568
Если все цифры идут по порядку, то просто поменять местами две посление.
Если полученное таким образом число ВНЕЗАПНО оказалось не больше исходного, вернем null. Такое возможно, например, для чисел вроде 1110. Если мы этот нолик переставим куда угодно, получится число меньше исходного.
Алгоритм у тебя уже есть, так что дерзай, LINQ тебе в помощь. Возникнут конкретные затруднения - задавай конкретные вопросы.
1. Поменять местами первую идущую не в порядке возрастания цифру на минимальную из оставшихся бОльших цифр.
2. Отсортировать оставшиеся цифры.
Например, есть число 12085640
Нолик не идет по порядку - меняем его на 4:
12485600
А теперь сортируем:
12400568
Если все цифры идут по порядку, то просто поменять местами две посление.
Если полученное таким образом число ВНЕЗАПНО оказалось не больше исходного, вернем null. Такое возможно, например, для чисел вроде 1110. Если мы этот нолик переставим куда угодно, получится число меньше исходного.
Алгоритм у тебя уже есть, так что дерзай, LINQ тебе в помощь. Возникнут конкретные затруднения - задавай конкретные вопросы.
Светлана Баргал
Спасибо большое за ответ! Но если нужно использовать только циклы и алгоритмы? Вопрос в том, как так отсортировать число?
... . next-bigger's People. Contributors. ... React. A declarative, efficient, and flexible JavaScript library for building user interfaces. Vue.js. Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web. Typescript. TypeScript is a superset of JavaScript that compiles to clean JavaScript output. TensorFlow. An Open Source Machine Learning Framework for Everyone. Django. The Web framework for perfectionists with deadlines. Laravel. A PHP framework for web artisans. D3. Bring data to life with SVG, Canvas and HTML.. Скрыть
Чтобы число было больше нужно, чтобы бóльшая цифра стояла в начале, а меньшая в конце. Так 12345 меньше чем 54321.
Чтобы получить следующее большее значение, нужно найти с конца первое число, которое не соответствует сортировке.
Для сортировки тут нам отлично подходит алгоритм сортировки маленького множества элементов - создаем массив для всех цифро от 0 до 9 и считаем сколько раз они встретились.
Алгоритм Юрия неправильный, т.к. его число больше моего, а значит не "следующее большое число".
string NextBiggerThan(string n) {
if (n == null || n.Length == 1)
{
return null;
}
string result = null;
var digits = new int[10];
var lastDigit = Convert.ToInt32(n[n.Length - 1].ToString());
digits[lastDigit]++;
for(var i = n.Length - 2; i >= 0 && result == null; i--)
{
var currentDigit = Convert.ToInt32(n[i].ToString());
digits[currentDigit]++;
if (currentDigit < lastDigit) {
var lastDigits = new StringBuilder(n.Length - i);
for (var digit = 9; digit >= 0; digit--)
{
var digitsCount = digits[digit];
if (digitsCount > 0)
{
lastDigits.Append(digit.ToString()[0], digitsCount);
}
}
if (i == 0)
{
result = lastDigits.ToString();
}
else
{
result = n.Substring(0, i) + lastDigits.ToString();
}
}
lastDigit = currentDigit;
}
return result;
}
Чтобы получить следующее большее значение, нужно найти с конца первое число, которое не соответствует сортировке.
Для сортировки тут нам отлично подходит алгоритм сортировки маленького множества элементов - создаем массив для всех цифро от 0 до 9 и считаем сколько раз они встретились.
Алгоритм Юрия неправильный, т.к. его число больше моего, а значит не "следующее большое число".
string NextBiggerThan(string n) {
if (n == null || n.Length == 1)
{
return null;
}
string result = null;
var digits = new int[10];
var lastDigit = Convert.ToInt32(n[n.Length - 1].ToString());
digits[lastDigit]++;
for(var i = n.Length - 2; i >= 0 && result == null; i--)
{
var currentDigit = Convert.ToInt32(n[i].ToString());
digits[currentDigit]++;
if (currentDigit < lastDigit) {
var lastDigits = new StringBuilder(n.Length - i);
for (var digit = 9; digit >= 0; digit--)
{
var digitsCount = digits[digit];
if (digitsCount > 0)
{
lastDigits.Append(digit.ToString()[0], digitsCount);
}
}
if (i == 0)
{
result = lastDigits.ToString();
}
else
{
result = n.Substring(0, i) + lastDigits.ToString();
}
}
lastDigit = currentDigit;
}
return result;
}
Светлана Баргал
Cпасибо большое за такой развернутый ответ, но возможно ли это реализовать не переводя в массив? Через рекурсию или циклы?
Светлана Баргал
Ааа, не увидела что у вас перевод в строку
Похожие вопросы
- Задание. В классе Program напишите следующие методы и вызовите их в главном методе Main:
- Найдите минимум методом дихотомии
- У меня есть такая проблема, может кто подскажет как можно правильно на WPF MVVM реализовать тестовую систему
- С# Разработайте и реализуйте собственный алгоритм, переводящий изображение в градациях серого цвета в цвет.
- Учитывая целое число n (n>2), напишите метод, который возвращает простые числа из диапазона [2, n].
- Аналитическая психотерапия, что это и какие методы или упражнения используются в данном методе.
- Как реализовать данное веб-приложение (сайт)
- Как реализовать данную таблицу?
- Зачем сажают морковь на грядке с клейстером? Хочу попробовать данный метод...
- Разработать класс описывающий множество точек на плоскости, реализовать метод который возвращает наименьшее расстояние