def unique(data):
    # 新建list
    new_list = []
    for item in data:
        # 原list中的項是否存在于新list中，不存在則添加。這是 O(n)操作
        if item not in new_list:
            new_list.append(item)
    return new_list

# 方法1：最基礎(chǔ)的線性查找
def unique_v1(data):
    new_list = []
    for item in data:
        # in 在列表上是 O(n) 掃描，整體 O(n2)
        # 該元素不在新list則添加
        if item not in new_list:
            new_list.append(item)
    return new_list

# 方法2：用下標遍歷
def unique_v2(data):
    new_list = []
    for i in range(len(data)):
        # 與第1種相同，遍歷方式換成range，復(fù)雜度不變
        if data[i] not in new_list:
            new_list.append(data[i])
    return new_list

# 方法3：列表推導(dǎo)式
def unique_v3(data):
    new_list = []
    # 利用列表推導(dǎo)式的副作用追加元素，寫法簡化，本質(zhì)與前面一樣
    [new_list.append(i) for i in data if i not in new_list]
    return new_list

# 方法4：通過元素首次出現(xiàn)位置判斷
def unique_v4(data):
    new_list = []
    for i in range(len(data)):
        # data.index(x) 返回 x 在 data 里第一次出現(xiàn)的下標
        # 當前下標恰好等于該值時，說明該元素是首次出現(xiàn)，將首次出現(xiàn)的添加到新list
        if i == data.index(data[i]):
            new_list.append(data[i])
    return new_list

# 方法5：原地刪除（從右往左掃描）
def unique_v5(data):
    l = len(data)
    while l > 0:
        l -= 1
        i = l
        while i > 0:
            i -= 1
            # 在 [0, l) 區(qū)間里尋找與 data[l] 相同的元素
            # 找到就刪后面那個，保留前面的
            if data[i] == data[l]:
                del data[l]
                break
    return data
# 修改原列表，空間 O(1)

# 方法6：原地刪除（從左往右掃）
def unique_v6(data):
    l = len(data)
    i = 0
    while i < l:
        j = i + 1
        while j < l:
            # 把 data[i] 后面所有等于它的元素刪掉
            if data[i] == data[j]:
                del data[j]
                l -= 1   # 列表變短，長度同步更新
            else:
                j += 1
        i += 1
    return data

# 方法7：用 try-except 替代 in
def unique_v7(data):
    new_list = []
    for item in data:
        try:
            # index 找不到會拋 ValueError
            new_list.index(item)
        except ValueError:
            # 找不到才追加
            new_list.append(item)
    return new_list
# 實際上不會這么使用——拿異常處理正常的控制流，性能和可讀性都吃虧

# 方法8：雙層循環(huán)+下標判斷
def unique_v8(data):
    new_list = []
    for i in range(len(data)):
        j = 0
        while j <= i:
            # 看 data[i] 在它之前是否出現(xiàn)過
            if data[i] == data[j]:
                # 只有 j == i（前面都沒遇到）時才追加
                if i == j:
                    new_list.append(data[i])
                break
            j += 1
    return new_list
# 內(nèi)層只跑到 i 而非 n，比較次數(shù)約為方法1的一半，但漸進復(fù)雜度仍是 O(n2)

# 方法9：set 配合 list——工程最常見寫法
def unique_v9(data):
    seen = set()        # set 用于 O(1) 判重
    result = []         # list 用于保持原順序
    for item in data:
        if item not in seen:
            seen.add(item)
            result.append(item)
    return result

# 方法10：dict.fromkeys()——最佳版本，實際使用首選
def unique_v10(data):
    # dict 自 Python 3.7 起保持插入順序
    # fromkeys 會自動用相同 key 覆蓋，從而完成去重
    return list(dict.fromkeys(data))

# 方法11：filter + 列表，函數(shù)式風(fēng)格
def unique_v11(data):
    seen = []
    # 內(nèi)部函數(shù)
    def check(item):
        # 閉包捕獲 seen
        # 注意 seen 是 list，in 仍是 O(n)，整體仍是 O(n2)
        if item not in seen:
            seen.append(item)
            return True
        return False
    return list(filter(check, data))
# 函數(shù)式風(fēng)格，但不純粹，seen 類型選錯了，這里只是為了展示寫法

# 方法12：filter + 字典，由list改為dict，仍然不是純函數(shù)式
def unique_v12(data):
    obj = {}
    def check(item):
        # 用 dict 替代上面的 list，查詢變成 O(1)
        if obj.get(item) is None:
            obj[item] = item
            return True
        return False
    return list(filter(check, data))

# 方法13：set 直接轉(zhuǎn)列表，常見用法
def unique_v13(data):
    # 哈希集合天然不重復(fù)
    return list(set(data))
# 寫法最短，但順序會被打亂

# 方法14：map + filter 組合
def unique_v14(data):
    seen = []
    def mark(item):
        # 第一次見到返回元素本身，后續(xù)返回 None
        if item not in seen:
            seen.append(item)
            return item
        return None
    # 先 map 標記，再 filter 把 None 去掉
    return list(filter(lambda x: x is not None, map(mark, data)))
# 函數(shù)式風(fēng)格，但 seen 用 list 仍是 O(n2)

# 方法15：先排序再相鄰去重（從右往左刪）
def unique_v15(data):
    data.sort()  # 排序后，相同元素會聚到一起
    l = len(data)
    while l > 0:
        l -= 1
        # 相鄰兩兩比較，相同就刪后面那個
        if l > 0 and data[l] == data[l-1]:
            del data[l]
    return data
# 復(fù)雜度由 sort 決定，O(nlogn)；元素需要可比較

# 方法16：先排序再相鄰去重（從左往右刪）
def unique_v16(data):
    data.sort()
    l = len(data) - 1
    i = 0
    while i < l:
        if data[i] == data[i+1]:
            del data[i]   # 刪當前，i 不前進；同時長度減一
            i -= 1
            l -= 1
        i += 1
    return data

# 方法17：reduce + 元組累加器（函數(shù)式風(fēng)格但能跑到 O(n)）
import functools

def unique_v17(data):
    def foo(acc, item):
        # 累加器是一個元組 (result, seen)
        # result 保留首次出現(xiàn)的順序，seen 用集合實現(xiàn) O(1) 判重
        result, seen = acc
        if item in seen:
            return (result, seen)
        # 這里直接修改累加器內(nèi)部的 list 和 set
        # 嚴格的純函數(shù)式應(yīng)返回新對象 (result + [item], seen | {item})
        # 但那樣每步都新建列表/集合，復(fù)雜度退回到 O(n2)
        # 在 reduce 內(nèi)做"受控副作用"，換取 O(n) 的性能
        seen.add(item)
        result.append(item)
        return (result, seen)

    # 初始累加器是空列表+空集合，最后取 [0] 即得到去重結(jié)果
    return functools.reduce(foo, data, ([], set()))[0]
# O(n)；保序；本質(zhì)是用 reduce 重寫了方法9的循環(huán)

# 方法18：調(diào)用 numpy.unique
def unique_v18(data):
    import numpy as np
    # numpy 底層用 C 實現(xiàn)的排序+相鄰去重
    return list(np.unique(np.array(data)))
# O(nlogn)；不保序；適合大規(guī)模數(shù)值數(shù)據(jù)

# 方法19：遞歸+原地刪除
def unique_v19(data, length=None):
    # 遞歸退出條件
    if length is None:
        length = len(data)
    if length <= 1:
        return data

    last_idx = length - 1
    # 看末尾元素是否在前面出現(xiàn)過
    is_repeat = False
    for i in range(last_idx):
        if data[i] == data[last_idx]:
            is_repeat = True
            break

    # 重復(fù)則刪除
    if is_repeat:
        del data[last_idx]

    # 遞歸調(diào)用，處理前 length-1 項
    return unique_v19(data, length - 1)
# 遞歸深度 = n，大數(shù)據(jù)會棧溢出，僅作學(xué)習(xí)用

# 方法20：遞歸+拼接返回（不修改原列表）
# 遞歸自后往前逐個調(diào)用，當長度為1時終止。與上一個遞歸不同，這里將不重復(fù)的項目作為結(jié)果拼接起來
def unique_v20(data, length=None):
    if length is None:
        length = len(data)
    if length <= 1:
        return data

    last_idx = length - 1
    last_item = data[last_idx]

    is_repeat = False
    for i in range(last_idx):
        if data[i] == last_item:
            is_repeat = True
            break

    # 末尾元素重復(fù)就丟棄，否則拼到結(jié)果末尾
    result = [] if is_repeat else [last_item]
    # 切片 + 拼接都會產(chǎn)生新列表，空間開銷大
    return unique_v20(data[:last_idx], length - 1) + result
# 演示如何用遞歸構(gòu)造結(jié)果，工程上沒有實用價值

# 保序、O(n)、對所有可哈希類型有效，Python 3.7+ 自帶
result = list(dict.fromkeys(data))

result = list(set(data))

import numpy as np
result = list(np.unique(data))

def unique_with_rule(data, key=None, on_duplicate=None):
    """
    帶邏輯干預(yù)的去重。

    key: 可哈希的去重鍵，默認拿元素本身
    on_duplicate: 遇到重復(fù)時如何處理 (舊值, 新值) -> 新的"代表值"
                  返回 None 時保持舊值不變（即等同于丟棄新值）
    """
    if key is None:
        key = lambda x: x

    chosen = {}     # 鍵 -> 當前選中的元素
    order  = []     # 記錄鍵首次出現(xiàn)的順序，保證保序

    for item in data:
        k = key(item)
        if k not in chosen:
            chosen[k] = item
            order.append(k)
        elif on_duplicate is not None:
            # 遇到重復(fù)時由調(diào)用方?jīng)Q定如何合并
            merged = on_duplicate(chosen[k], item)
            if merged is not None:
                chosen[k] = merged

    return [chosen[k] for k in order]

students = [
    {'id': 1, 'name': '張三', 'score': 90},
    {'id': 1, 'name': '張三', 'score': 95},   # 同 id，分數(shù)更高
    {'id': 2, 'name': '李四',   'score': 99},
]
result = unique_with_rule(
    students,
    key=lambda x: x['id'],
    on_duplicate=lambda old, new: new if new['score'] > old['score'] else old,
)
# [{'id':1,'score':95,...}, {'id':2,'score':99,...}]

from collections import Counter

data = ['A', 'B', 'A', 'C', 'B', 'A']
# Counter 本身就是"鍵->計數(shù)"，遍歷一次即可完成統(tǒng)計
counts = Counter(data)
# Python 3.7+ 起 dict / Counter 保留插入順序，因此 keys 即首次出現(xiàn)順序
unique_keys = list(counts.keys())
# unique_keys = ['A', 'B', 'C']
# counts      = {'A': 3, 'B': 2, 'C': 1}

data = [5, 12, 5, 100, 12, 200]
seen = set()
result = []
for x in data:
    if 0 <= x <= 50:
        # 區(qū)間內(nèi)才參與去重
        if x in seen:
            continue
        seen.add(x)
    # 區(qū)間外或首次出現(xiàn)，都保留
    result.append(x)
# [5, 12, 100, 200]

def deduplicate_with_key(data, key=None):
    """按自定義 key 去重，保留首次出現(xiàn)的元素"""
    if key is None:
        return list(dict.fromkeys(data))

    seen = set()
    result = []
    for item in data:
        # 把不可哈希的整體映射成可哈希的鍵
        k = key(item)
        if k not in seen:
            seen.add(k)
            result.append(item)
    return result

# 使用示例：按學(xué)生 id 去重
students = [
    {'id': 1, 'name': '張三', 'score': 90},
    {'id': 1, 'name': '張三', 'score': 95},   # id 重復(fù)
    {'id': 2, 'name': '李四', 'score': 85},
]
result = deduplicate_with_key(students, key=lambda x: x['id'])
# 只保留第一個 id=1 的學(xué)生

def deduplicate_short(data):
    seen = set()
    # x in seen 為 False 時才會執(zhí)行 seen.add(x)
    # add 返回 None 讓 or 短路，整個表達式得到 False，于是元素被保留
    return [x for x in data if not (x in seen or seen.add(x))]