?LeetCode刷題實(shí)戰(zhàn)80：刪除排序數(shù)組中的重復(fù)項(xiàng) II
算法的重要性，我就不多說(shuō)了吧，想去大廠，就必須要經(jīng)過(guò)基礎(chǔ)知識(shí)和業(yè)務(wù)邏輯面試+算法面試。所以，為了提高大家的算法能力，這個(gè)公眾號(hào)后續(xù)每天帶大家做一道算法題，題目就從LeetCode上面選 ！
今天和大家聊的問(wèn)題叫做?刪除排序數(shù)組中的重復(fù)項(xiàng) II，我們先來(lái)看題面：
https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array-ii/
Given a sorted array nums, remove the duplicates in-place such that duplicates appeared at most twice and return the new length.
Do not allocate extra space for another array; you must do this by modifying the input array in-place with O(1) extra memory.
題意
示例 1：
輸入：nums = [1,1,1,2,2,3]
輸出：5, nums = [1,1,2,2,3]
解釋：函數(shù)應(yīng)返回新長(zhǎng)度 length = 5, 并且原數(shù)組的前五個(gè)元素被修改為 1, 1, 2, 2, 3 。你不需要考慮數(shù)組中超出新長(zhǎng)度后面的元素。
示例 2：
輸入：nums = [0,0,1,1,1,1,2,3,3]
輸出：7, nums = [0,0,1,1,2,3,3]
解釋：函數(shù)應(yīng)返回新長(zhǎng)度 length = 7, 并且原數(shù)組的前五個(gè)元素被修改為?0, 0, 1, 1, 2, 3, 3 。你不需要考慮數(shù)組中超出新長(zhǎng)度后面的元素。
解題
題解
new_nums = []
cur = None
for?i in range(n):
????if?cur == nums[i]:
????????count?+= 1
?else:
????????count?= 1
????????cur = nums[i]
????if?count?> 2:
????????continue
????new_nums.append(nums[i])
class?Solution:
????def?removeDuplicates(self, nums: List[int])?-> int:
????????# start是起始覆蓋指針，指向第一個(gè)可以覆蓋的位置
????????start, cur, cnt = 0, None, 0
????????n = len(nums)
????????if?n == 0:
????????????return?0
????????for?i in?range(n):
????????????if?cur == nums[i]:
????????????????cnt += 1
????????????else:
????????????????cnt = 1
????????????????cur = nums[i]
????????????# 如果數(shù)量超過(guò)2，說(shuō)明當(dāng)前元素應(yīng)該舍棄，則continue
????????????if?cnt > 2:
????????????????continue
????????????# 否則用當(dāng)前元素覆蓋start位置，并且start移動(dòng)一位
????????????else:
????????????????nums[start] = nums[i]
????????????????start += 1
????????return?start
class?Solution(object):
????def?removeDuplicates(self, nums):
????????"""
????????:type nums: List[int]
????????:rtype: int
????????"""
????????i = 0
????????for?n in?nums:
????????????if?i < 2?or?n != nums[i - 2]:
????????????????nums[i] = n
????????????????i += 1
????????return?i
上期推文：