In-Place Array Deletion , Filter and Compression

Array Deletion

用途：刪除、壓縮或過濾
維持 [0, slow) 一定滿足條件

int filterInPlace(vector<int>& nums, Pred keep) {
	int n = static_cast<int>(nums.size());
    int slow = 0;
    for (int fast = 0; fast < n; fast++) {
        if (keep(nums[fast])) {        // 決定要不要保留
            nums[slow] = nums[fast];   // 覆蓋寫到前面
            slow++;
        }
    }
    return slow; // 新長度
}

LeetCode Questions:

Array Compression

陣列是排序好的，有重複一定是連再一起
目標：[0, slow) 維持去重複的序列
想像：slow - 1是最後一個放入答案的值
如果相同，代表前面已經有k個一樣的->不保留
如果不同，表示還沒超過k次->可以保留

// k 是每個值最多保留k次
int removeDuplicates(vector<int>& nums, int k) {
	int n = static_cast<int>(nums.size());
	if (n <= k) return n;
	// maintain [0, slow) have no duplicates and keeps the order.
	int slow = k;
	for (int fast = k; fast < m; fast++) {
		if (nums[fast] != nums[slow-k]) {
			nums[slow] = nums[fast];
			slow++;
		}
	}
	return slow;
}