Почему это работает
- Всё левее write — уже ответ, и он отсортирован. Если nums[read] равно nums[write - 2], то оно равно и всему между ними: ответ уже кончается двумя такими числами, и третье лишнее.
- Соседа мало: равные соседи говорят только, что число повторяется, а не сколько раз его уже оставили. В 1, 1, 1 вторая и третья единица рядом с соседом выглядят одинаково, но убрать нужно только третью. nums[write - 2] считает за нас.
- Не больше k раз: первые k чисел оставляем, а сравниваем с nums[write - k]. При k = 1 это задача 26, Remove Duplicates from Sorted Array.
Сложность
Время O(n): read проходит массив один раз, на каждом шаге — одно сравнение и не больше одного копирования. Память O(1): массив переписываем на месте, сбоку только два индекса.
дальшеТеперь реши её сам, без подсказок.
Решить на LeetCode ↗