Проблема: Leetcode 80 – Удалить дубликаты из отсортированного массива II
Ссылка на проблему: https://leetcode.com/problems/remove-duplicates-from-sorted-array-ii/
Простое описание: Учитывая отсортированный массив, удалите вхождения чисел, которые повторяются более двух раз.
Так, например, данный массив равен [1,1,1,2,2,3]. Здесь 1 повторяется три раза, поэтому нам нужно сохранить только два вхождения одного. 2 повторяется два раза, что удовлетворяет нашим критериям. 3 повторяется только один раз, поэтому он находится в пределах нашего граничного условия. Итак, после того, как мы решили проблему, у нас должен быть наш массив в виде [1, 1, 2, 2, 3] делаем длину массива равной 5. Загвоздка в том, что мы должны изменить фактический входной массив и решить это в O (1) пространственной сложности.
Решение на Java:
class Solution {
public int removeDuplicates(int[] nums) {
int n = nums.length;
int duplicatesAllowed = 2;
int start = duplicatesAllowed;
int end = duplicatesAllowed;
while (end < n) {
if (nums[start - duplicatesAllowed] != nums[end]) {
nums[start++] = nums[end];
}
end++;
}
return start;
}
}
Таким образом, эта проблема может быть расширена для любого количества разрешенных дубликатов. Нам нужно найти общее решение. Мы считаем, что дубликаты разрешены как два в приведенной выше задаче. У нас есть два указателя start и конец и установите их равными разрешенные дубликаты изначально. Теперь мы всегда проверяем, разрешено ли start - duplicates равно нашему текущему элементу, т.е. nums[end] . Если это не так, то мы обновляем значение nums[start равным nums[end] и увеличиваем указатель start .
Сделав это, мы сможем ограничить количество вхождений чисел меньшим или равным Разрешенные дубликаты .
Эта техника называется “Техника двух указателей”.
Оригинал: “https://dev.to/varunu28/a-leetcode-a-day-remove-duplicates-from-sorted-array-ii-2b0”