LeetCode 解題思路：27. Remove Element（移除元素）

# 原始陣列
nums = [3,2,2,3], val = 3

# 執行後的實際狀況
nums = [2,2,2,3]  # 後面仍然有數字！
        ↑───↑
      只看這部分

# 題目用 _ 表示
nums = [2,2,_,_]  # 只是說後面不重要

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        # 慢指針，指向下一個要填入的位置
        i = 0
        
        # 快指針，遍歷整個陣列
        for j in range(len(nums)):
            # 如果當前元素不等於 val，保留它
            if nums[j] != val:
                nums[i] = nums[j]
                i += 1
        
        return i

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        i = 0
        n = len(nums)
        
        while i < n:
            if nums[i] == val:
                # 將當前元素與最後一個元素交換
                nums[i] = nums[n - 1]
                # 縮小考慮範圍
                n -= 1
                # 注意：不要 i += 1，因為交換來的元素也需要檢查
            else:
                i += 1
        
        return n

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        left = 0
        right = len(nums) - 1
        
        while left <= right:
            if nums[left] == val:
                # 用右邊的元素覆蓋
                nums[left] = nums[right]
                right -= 1
            else:
                left += 1
        
        return left

# ❌ 錯誤！不是原地演算法
def removeElement(self, nums: List[int], val: int) -> int:
    result = []
    for num in nums:
        if num != val:
            result.append(num)
    
    nums[:] = result  # 即使複製回去也不對
    return len(result)

# ❌ 錯誤！remove() 每次只刪除一個，且時間複雜度是 O(n)
def removeElement(self, nums: List[int], val: int) -> int:
    while val in nums:
        nums.remove(val)  # 總時間複雜度變成 O(n²)
    return len(nums)

# ❌ 錯誤示範
def removeElement(self, nums: List[int], val: int) -> int:
    i = 0
    n = len(nums)
    
    while i < n:
        if nums[i] == val:
            nums[i] = nums[n - 1]
            n -= 1
            i += 1  # 錯誤！交換來的元素可能也是 val
        else:
            i += 1
    
    return n

def removeElement_preserve_order(nums, val):
    write_idx = 0
    
    for read_idx in range(len(nums)):
        if nums[read_idx] != val:
            nums[write_idx] = nums[read_idx]
            write_idx += 1
    
    return write_idx

def removeElementWithCount(nums, val):
    original_len = len(nums)
    k = removeElement(nums, val)
    removed_count = original_len - k
    
    print(f"刪除了 {removed_count} 個 {val}")
    return k, removed_count

def markElement(nums, val, mark=-1):
    """將所有 val 標記為 mark"""
    count = 0
    for i in range(len(nums)):
        if nums[i] == val:
            nums[i] = mark
            count += 1
    return len(nums) - count

def removeElement_adaptive(nums, val):
    # 快速統計 val 的數量
    val_count = nums.count(val)
    
    # 如果 val 很少，使用交換法
    if val_count < len(nums) // 4:
        return removeElement_swap(nums, val)
    else:
        return removeElement_standard(nums, val)

def removeMultipleValues(nums, vals):
    """移除多個值"""
    vals_set = set(vals)
    write_idx = 0
    
    for num in nums:
        if num not in vals_set:
            nums[write_idx] = num
            write_idx += 1
    
    return write_idx

def test_removeElement():
    test_cases = [
        # (nums, val, expected_k, possible_results)
        ([3,2,2,3], 3, 2, [[2,2]]),
        ([0,1,2,2,3,0,4,2], 2, 5, [[0,1,3,0,4], [0,1,4,0,3]]),
        ([], 1, 0, [[]]),
        ([1], 1, 0, [[]]),
        ([1], 2, 1, [[1]]),
        ([1,1,1,1], 1, 0, [[]]),
        ([1,2,3,4,5], 3, 4, [[1,2,4,5]]),
    ]
    
    solution = Solution()
    for nums, val, expected_k, possible_results in test_cases:
        nums_copy = nums.copy()
        k = solution.removeElement(nums_copy, val)
        
        assert k == expected_k
        # 檢查前 k 個元素都不等於 val
        assert all(nums_copy[i] != val for i in range(k))
        
        print(f"✅ 通過：{nums} 移除 {val} → k={k}")