12 · 技巧专题

来源： 位运算、摩尔投票、荷兰国旗等经典算法技巧
核心价值： 用巧妙的数学性质或算法技巧，解决特定类型的问题
题量： 5 题

---

一、位运算

核心性质

运算	规则	用途
a ^ 0 = a	任何数与 0 异或不变	保留原值
a ^ a = 0	任何数与自身异或为 0	消除成对出现的数
a ^ b ^ a = b	异或满足交换律和结合律	找唯一出现一次的数
a & (-a)	取最低位的 1	树状数组、位运算技巧

⭐ 只出现一次的数字

def single_number(nums):
    res = 0
    for num in nums:
        res ^= num
    return res

---

二、摩尔投票法

核心思想

不同元素互相抵消，最后剩下的就是众数（出现次数 > n/2 的候选）。

def majority_element(nums):
    candidate = nums[0]
    count = 1
    
    for num in nums[1:]:
        if count == 0:
            candidate = num
            count = 1
        elif num == candidate:
            count += 1
        else:
            count -= 1
    
    return candidate

---

三、荷兰国旗问题（三指针）

核心思想

用三个指针（p0, p1, p2）将数组分为三个区域：0 区、1 区（处理区）、2 区。

def sort_colors(nums):
    p0 = 0          # 0 的右边界
    cur = 0         # 当前处理位置
    p2 = len(nums) - 1  # 2 的左边界
    
    while cur <= p2:
        if nums[cur] == 0:
            nums[p0], nums[cur] = nums[cur], nums[p0]
            p0 += 1
            cur += 1
        elif nums[cur] == 2:
            nums[p2], nums[cur] = nums[cur], nums[p2]
            p2 -= 1
            # cur 不 +1，因为交换过来的值还没处理
        else:  # nums[cur] == 1
            cur += 1

---

四、下一个排列

核心步骤

1. 从右往左找第一个「升序对」(i, i+1)，即 nums[i] < nums[i+1]
2. 从右往左找第一个比 nums[i] 大的元素 nums[j]
3. 交换 nums[i] 和 nums[j]
4. 翻转 i+1 到末尾（使其变为升序/最小排列）

def next_permutation(nums):
    # 1. 找第一个升序对
    i = len(nums) - 2
    while i >= 0 and nums[i] >= nums[i + 1]:
        i -= 1
    
    if i >= 0:
        # 2. 找第一个比 nums[i] 大的
        j = len(nums) - 1
        while j >= 0 and nums[j] <= nums[i]:
            j -= 1
        # 3. 交换
        nums[i], nums[j] = nums[j], nums[i]
    
    # 4. 翻转 i+1 到末尾
    left, right = i + 1, len(nums) - 1
    while left < right:
        nums[left], nums[right] = nums[right], nums[left]
        left += 1
        right -= 1

---

五、Floyd 判圈法（双指针找重复数）

把数组看成链表：nums[i] 的值表示下一个节点的索引。
有重复数 = 有环，找环入口 = 找重复数。

def find_duplicate(nums):
    slow = fast = nums[0]
    
    # 第一阶段：快慢指针相遇
    while True:
        slow = nums[slow]
        fast = nums[nums[fast]]
        if slow == fast:
            break
    
    # 第二阶段：找环入口
    slow = nums[0]
    while slow != fast:
        slow = nums[slow]
        fast = nums[fast]
    
    return slow

---

六、Hot 100 技巧题目清单

题号	题目	难度	核心技巧	建议用时
136	只出现一次的数字	Easy	异或	15 min
169	多数元素	Easy	摩尔投票	15 min
75	颜色分类	Medium	三指针（荷兰国旗）	25 min
31	下一个排列	Medium	三步法	30 min
287	寻找重复数	Medium	Floyd 判圈	30 min

---

七、参考与延伸

• 02-双指针与滑动窗口（荷兰国旗 = 三指针变体）
• 04-链表（Floyd 判圈法在链表中常见）