Вопрос

Учитывая строку 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 в приведенном выше коде)
  • Отбросить термины, не являющиеся доминирующими

Код