快慢指針的在leetcode的問題中有很多應(yīng)用，例如通過一次遍歷找到鏈表的中間節(jié)點(diǎn)。 這里要介紹的是作為哨兵，應(yīng)用于數(shù)組或者鏈表中刪除特定元素，不另外開辟空間，即空間復(fù)雜度為O(1)
刪除有序數(shù)組中的重復(fù)項
在這里插入圖片描述
在這里插入圖片描述
因?yàn)槭怯行驍?shù)組，所以重復(fù)的元素都是在一起的。暴力處理，每次判斷當(dāng)前元素和后一個元素是否相同，不相同則刪除，而刪除需要移動后面的元素，時間復(fù)雜度為
O(n^2)
使用快慢指針，slow記錄的是不同元素的索引。fast作為哨兵，一開始指向slow的下一個元素，如果遇到不同的元素則賦值給slow， 最后返回數(shù)組的長度為slow + 1（索引從0開始，長度需要+1）。 此時數(shù)組中的前 slow + 1個元素都有不同的值。
代碼如下：
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
if len(nums) == 0:
return 0
slow = 0
nums_len = len(nums)
for fast in range(1,nums_len):
if nums[fast] != nums[slow]:
slow += 1
nums[slow] = nums[fast]
return slow + 1
時間復(fù)雜度為：O(n)
空間復(fù)雜第為： O(1)
刪除排序鏈表中的重復(fù)元素
在這里插入圖片描述
在這里插入圖片描述
方法和上一題一樣，這里需要注意，鏈表需要將slow的下一個節(jié)點(diǎn)置為None
代碼如下：
class Solution:
def deleteDuplicates(self, head: ListNode) -> ListNode:
if not head:
return None
slow,fast = head,head
while fast.next:
fast = fast.next
if fast.val != slow.val:
slow = slow.next
slow.val = fast.val
slow.next = None
return head
時間復(fù)雜度為：O(n)
空間復(fù)雜第為： O(1)
移除特定元素
在這里插入圖片描述
在這里插入圖片描述
同樣利用使用快慢指針。
slow初始值為-1，不指向任何元素，因?yàn)橛锌赡苷麄€數(shù)組都是待刪除的元素。fast作為哨兵，從頭遍歷。如果遇到不等于val的元素則賦值給slow， 最后返回數(shù)組的長度為slow + 1。
代碼如下：
class Solution:
def removeElement(self, nums: List[int], val: int) -> int:
if len(nums) == 0:
return 0
nums_len = len(nums)
slow = -1 #
for fast in range(nums_len):
if nums[fast] != val:
slow += 1
nums[slow] = nums[fast]
return slow + 1
時間復(fù)雜度為：O(n)
空間復(fù)雜第為： O(1)
移動零
在這里插入圖片描述
思路于上面一個問題一樣，只不過這里不是移除元素0，而是要將元素0移至末尾，因此這里要進(jìn)行元素的交換，而不是直接賦值
代碼如下：
class Solution:
def moveZeroes(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
if len(nums)==0:
return
slow = -1
nums_len = len(nums)
for fast in range(nums_len):
if nums[fast] != 0:
slow += 1
# 進(jìn)行元素的交換，而不是直接賦值
tmp = nums[slow]
nums[slow] = nums[fast]
nums[fast] = tmp
時間復(fù)雜度為：O(n)
空間復(fù)雜第為： O(1)
