Учитывая строку num, представляющую неотрицательное целое число num
, и целое число k
, вернуть наименьшее возможное целое число после удаления k
цифр из num
.
Пример 1:
Input: num = "1432219", k = 3 Output: "1219" Explanation: Remove the three digits 4, 3, and 2 to form the new number 1219 which is the smallest.
Пример 2:
Input: num = "10200", k = 1 Output: "200" Explanation: Remove the leading 1 and the number is 200. Note that the output must not contain leading zeroes.
Пример 3:
Input: num = "10", k = 2 Output: "0" Explanation: Remove all the digits from the number and it is left with nothing which is 0.
Ограничения:
1 <= k <= num.length <= 105
num
состоит только из цифр.num
не имеет начальных нулей, кроме самого нуля.
Java-решение
Я написал два решения для одной и той же проблемы с двумя разными временными сложностями.
O(kn)
Где k — количество элементов, которые можно удалить из строки, а n — размер этой строки
Для каждой k-й позиции я иду через n элементов каждый раз, так что K * N
Код
O(n)
В приведенном ниже коде может показаться, что временная сложность приведенного ниже кода не может быть N из-за этого вложенного цикла, поэтому внешний цикл будет выполняться через все элементы, поэтому O (n) для этого, и внутренний цикл в худшем случае будет проходить через все элементы в строке, но только один раз, поэтому, объединив два, мы получим O (2n), отбрасывая постоянное значение, которое у нас есть На).
Вы можете подумать, что в коде есть и другие циклы, для этого вам нужно запомнить следующие 4 правила Big :O
- Если у вас есть два разных шага в вашем алгоритме, вы должны добавить эти шаги
- Отбросьте константы (в большинстве случаев они имеют значение)
- Разные входы, разные переменные (например, k и n в приведенном выше коде)
- Отбросить термины, не являющиеся доминирующими