LeetCode 解題思路：26. Remove Duplicates From Sorted Array（刪除有序陣列中的重複項）

# ✅ 非遞減順序的例子
[1, 2, 3, 4, 5]      # 嚴格遞增
[1, 1, 2, 2, 3]      # 有重複值（這題的重點！）
[5, 5, 5, 5, 5]      # 全部相同
[1, 2, 2, 3, 3, 3]   # 部分重複

# ❌ 不是非遞減順序
[5, 4, 3, 2, 1]      # 遞減
[1, 3, 2, 4]         # 有下降

# ❌ 錯誤示範：不是原地演算法
def removeDuplicates_wrong(nums):
    unique_nums = []  # 創建新陣列！
    for num in nums:
        if num not in unique_nums:
            unique_nums.append(num)
    return len(unique_nums)

# ✅ 正確示範：原地修改
def removeDuplicates_correct(nums):
    # 只用幾個變數，直接修改 nums
    i = 0
    for j in range(1, len(nums)):
        if nums[j] != nums[i]:
            i += 1
            nums[i] = nums[j]
    return i + 1

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        if not nums:
            return 0
        
        # 慢指針，指向最後一個不重複元素的位置
        i = 0
        
        # 快指針，從第二個元素開始遍歷
        for j in range(1, len(nums)):
            # 發現不同的元素
            if nums[j] != nums[i]:
                i += 1
                nums[i] = nums[j]
        
        # i 是索引，長度要加 1
        return i + 1

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        if not nums:
            return 0
        
        # k 表示目前有多少個唯一元素
        k = 1  # 第一個元素肯定是唯一的
        
        for i in range(1, len(nums)):
            # 如果當前元素與前一個不同，就是新的唯一元素
            if nums[i] != nums[i - 1]:
                nums[k] = nums[i]  # 放到第 k 個位置
                k += 1             # 唯一元素數量加 1
        
        return k

# ❌ 錯誤！創建了新陣列
def removeDuplicates(self, nums: List[int]) -> int:
    unique = []
    for num in nums:
        if not unique or num != unique[-1]:
            unique.append(num)
    
    # 即使複製回去也不對，因為過程中用了 O(n) 空間
    nums[:] = unique
    return len(unique)

# ❌ 效率低下！沒有利用排序特性
def removeDuplicates(self, nums: List[int]) -> int:
    i = 0
    for j in range(len(nums)):
        # 檢查 nums[j] 是否在前面出現過
        if nums[j] not in nums[:i]:  # O(n) 操作！
            nums[i] = nums[j]
            i += 1
    return i

# ❌ 常見錯誤
def removeDuplicates(self, nums: List[int]) -> int:
    # ... 處理邏輯 ...
    return i  # 錯誤！i 是最後一個元素的索引，應該返回 i + 1

# 方法 1：先排序（改變了相對順序）
def removeDuplicates_unsorted_v1(nums):
    nums.sort()  # O(n log n)
    # 然後用原本的方法
    
# 方法 2：使用額外空間（不是原地）
def removeDuplicates_unsorted_v2(nums):
    seen = set()
    k = 0
    for num in nums:
        if num not in seen:
            seen.add(num)
            nums[k] = num
            k += 1
    return k

def removeDuplicates(self, nums: List[int], k: int) -> int:
    if len(nums) <= k:
        return len(nums)
    
    # i 指向下一個要填入的位置
    i = k
    
    for j in range(k, len(nums)):
        # 與第 i-k 個位置比較
        if nums[j] != nums[i - k]:
            nums[i] = nums[j]
            i += 1
    
    return i

def removeDuplicatesWithCount(self, nums: List[int]) -> tuple:
    original_length = len(nums)
    unique_length = self.removeDuplicates(nums)
    removed_count = original_length - unique_length
    
    print(f"原始長度：{original_length}")
    print(f"唯一元素：{unique_length}")
    print(f"刪除數量：{removed_count}")
    
    return unique_length, removed_count

def twoPointers(nums):
    # 慢指針：維護結果
    slow = 0
    
    # 快指針：探索元素
    for fast in range(len(nums)):
        if 滿足某條件:
            nums[slow] = nums[fast]
            slow += 1
    
    return slow

def removeDuplicates(self, nums: List[int]) -> int:
    if not nums:
        return 0
    
    i = 0
    print(f"初始: nums = {nums}")
    
    for j in range(1, len(nums)):
        if nums[j] != nums[i]:
            i += 1
            nums[i] = nums[j]
            print(f"Step {j}: 發現新元素 {nums[j]}")
            print(f"        nums = {nums[:i+1]} | {nums[i+1:]}")
    
    return i + 1

def test_removeDuplicates():
    test_cases = [
        # [輸入, 預期輸出, 預期陣列前綴]
        ([], 0, []),
        ([1], 1, [1]),
        ([1,1,1,1,1], 1, [1]),
        ([1,2,3,4,5], 5, [1,2,3,4,5]),
        ([1,1,2,2,3,3], 3, [1,2,3]),
        ([-1,0,0,0,3,3], 3, [-1,0,3]),
        ([1,1,2], 2, [1,2])
    ]
    
    solution = Solution()
    for nums, expected_k, expected_prefix in test_cases:
        nums_copy = nums.copy()
        k = solution.removeDuplicates(nums_copy)
        assert k == expected_k
        assert nums_copy[:k] == expected_prefix
        print(f"✅ 通過：{nums} -> {k}")