单序列原地修改 One Sequence Two Pointers In-Place Modification¶
Table of Contents¶
- 27. Remove Element (Easy)
- 26. Remove Duplicates from Sorted Array (Easy)
- 80. Remove Duplicates from Sorted Array II (Medium)
- 2273. Find Resultant Array After Removing Anagrams (Easy)
- 283. Move Zeroes (Easy)
- 905. Sort Array By Parity (Easy)
- 922. Sort Array By Parity II (Easy)
- 2460. Apply Operations to an Array (Easy)
- 1089. Duplicate Zeros (Easy)
- 75. Sort Colors (Medium)
27. Remove Element¶
"""
- Remove all instances of a given value in-place.
"""
from typing import List
# Fast Slow Pointers
def removeElement(nums: List[int], val: int) -> int:
fast, slow = 0, 0
while fast < len(nums):
if nums[fast] != val:
nums[slow] = nums[fast]
slow += 1
fast += 1
return slow
nums = [0, 1, 2, 2, 3, 0, 4, 2]
val = 2
print(removeElement(nums, val)) # 5
#include <iostream>
#include <vector>
using namespace std;
// Fast Slow Pointers
int removeElement(vector<int>& nums, int val) {
size_t n = nums.size();
size_t slow = 0, fast = 0;
while (fast < n) {
if (nums[fast] != val) {
nums[slow] = nums[fast];
slow++;
}
fast++;
}
return (int)slow;
}
int main() {
vector<int> nums = {3, 2, 2, 3};
int val = 3;
cout << removeElement(nums, val) << endl; // 2
return 0;
}
26. Remove Duplicates from Sorted Array¶
#include <cassert>
#include <vector>
using namespace std;
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
int fast = 1, slow = 1;
int n = nums.size();
while (fast < n) {
if (nums[fast] != nums[fast - 1]) {
nums[slow] = nums[fast];
slow++;
}
fast++;
}
return slow;
}
};
int main() {
Solution solution;
vector<int> nums = {0, 0, 1, 1, 1, 2, 2, 3, 3, 4};
assert(solution.removeDuplicates(nums) == 5);
return 0;
}
80. Remove Duplicates from Sorted Array II¶
"""
- Allow at most two duplicates.
- fast pointer: explore the array
- slow pointer: point to the position to be replaced
"""
from typing import List
def removeDuplicates(nums: List[int]) -> int:
if len(nums) <= 2:
return len(nums)
fast, slow = 2, 2
while fast < len(nums):
if nums[fast] != nums[slow - 2]:
nums[slow] = nums[fast]
slow += 1
fast += 1
return slow
nums = [1, 1, 1, 2, 2, 3]
print(removeDuplicates(nums))
#include <cassert>
#include <vector>
using namespace std;
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
int n = nums.size();
if (n <= 2) return n;
int fast = 2, slow = 2;
while (fast < n) {
if (nums[fast] != nums[slow - 2]) {
nums[slow] = nums[fast];
slow++;
}
fast++;
}
return slow;
}
};
int main() {
Solution solution;
vector<int> nums = {0, 0, 1, 1, 1, 1, 2, 2, 3, 3, 4};
assert(solution.removeDuplicates(nums) == 9);
return 0;
}
2273. Find Resultant Array After Removing Anagrams¶
283. Move Zeroes¶
"""
- Move all zeroes to the end of the array while maintaining the relative order of the non-zero elements.
"""
from typing import List
def moveZeroes(nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
fast, slow = 0, 0
while fast < len(nums):
if nums[fast] != 0:
nums[slow], nums[fast] = nums[fast], nums[slow]
slow += 1
fast += 1
nums = [0, 1, 0, 3, 12]
moveZeroes(nums)
print(nums) # [1, 3, 12, 0, 0]
#include <iostream>
#include <vector>
using namespace std;
void moveZeroes(vector<int>& nums) {
size_t n = nums.size();
size_t fast = 0, slow = 0;
while (fast < n) {
if (nums[fast] != 0) {
swap(nums[slow], nums[fast]);
slow++;
}
fast++;
}
}
int main() {
vector<int> nums = {0, 1, 0, 3, 12};
moveZeroes(nums);
// [1, 3, 12, 0, 0]
for (size_t i = 0; i < nums.size(); i++) {
cout << nums[i] << " ";
}
cout << endl;
return 0;
}
905. Sort Array By Parity¶
from typing import List
# Left Right Pointers
def sortArrayByParityLR(nums: List[int]) -> List[int]:
left, right = 0, len(nums) - 1
while left < right:
if not nums[left] % 2:
left += 1
else:
while left < right and nums[right] % 2:
right -= 1
nums[left], nums[right] = nums[right], nums[left]
return nums
# Fast Slow Pointers
def sortArrayByParityFS(nums: List[int]) -> List[int]:
n = len(nums)
fast, slow = 0, 0
while fast < n:
if not nums[fast] % 2:
nums[slow], nums[fast] = nums[fast], nums[slow]
slow += 1
fast += 1
return nums
nums = [3, 1, 2, 4]
print(sortArrayByParityLR(nums)) # [4, 2, 1, 3]
print(sortArrayByParityFS(nums)) # [4, 2, 1, 3]
922. Sort Array By Parity II¶
2460. Apply Operations to an Array¶
1089. Duplicate Zeros¶
"""
- Duplicate each occurrence of zero, shifting the remaining elements to the right.
"""
from typing import List
def duplicateZeros(arr: List[int]) -> None:
"""
Do not return anything, modify arr in-place instead.
"""
n = len(arr)
fast, slow = 0, 0
# First pass: find the position
# where the last element would be in the expanded array
while fast < n:
if arr[slow] == 0:
fast += 1
slow += 1
fast += 1
slow -= 1
fast -= 1
# Second pass: move elements backwards
while slow >= 0:
if fast < n:
arr[fast] = arr[slow]
if arr[slow] == 0:
fast -= 1
if fast < n:
arr[fast] = 0
slow -= 1
fast -= 1
arr = [1, 0, 2, 3, 0, 4, 5, 0]
duplicateZeros(arr)
print(arr) # [1, 0, 0, 2, 3, 0, 0, 4]
75. Sort Colors¶
from copy import deepcopy
from typing import List
# Left Right Pointers
def sort_colors_lr_pointers(nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
n = len(nums)
left = 0
for right in range(n):
if nums[right] == 0:
nums[left], nums[right] = nums[right], nums[left]
left += 1
for right in range(left, n):
if nums[right] == 1:
nums[left], nums[right] = nums[right], nums[left]
left += 1
# Three Pointers
def sort_colors_three_pointers(nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
left, right = 0, len(nums) - 1
cur = 0
while cur <= right:
if nums[cur] == 0:
nums[left], nums[cur] = nums[cur], nums[left]
left += 1
cur += 1
elif nums[cur] == 2:
nums[right], nums[cur] = nums[cur], nums[right]
right -= 1
else:
cur += 1
nums = [2, 0, 2, 1, 1, 0]
nums1, nums2 = deepcopy(nums), deepcopy(nums)
sort_colors_lr_pointers(nums1)
print(nums1) # [0, 0, 1, 1, 2, 2]
sort_colors_three_pointers(nums2)
print(nums2) # [0, 0, 1, 1, 2, 2]