algo-aha

其他数出现3次、一个数出现1次，求这单个数

• https://leetcode.com/problems/single-number-ii/

int singleNumber(vector<int>& nums) {
    // 泛化成：其他数出现k次，某个数出现p次（p不能被k整除），找这单个数
    // bit运算各个位相互独立，下面用int同时操作所有位，逻辑上把整个int当作一个bit（nums[i]也当作一个bit）
    // 要统计某位上出现1的次数，需要个mod k计数器（该计数器共m>=lgk位），设bm,..,b2,b1表示该计数器的位，
    // 1. 进位规则：从最高位开始更新，后面位和新数num都为1时进位
    //    ..., b3^=b2&b1&num, b2^=b1&num, b1^=num
    // 2. 计数为k时直接清零：
    //    当bm,..,b1的各个位分别等于k的各个位km,..,k1时计数为k，判断计数为k的表达式
    //    为expr_count_k=(bm_km)&..&(b1_k1)。分量(bj_kj)表示于kj==1时取bj、kj==0时取~bj
    //    清零的 mask = ~(expr_count_k)，清零：..., b3&=mask, b2&=mask, b1&=mask
    // 3. 最终各逻辑位”合并或“：b1|b2|b3...
    int b1 = 0, b2 = 0;
    int mask = 0;
    for (int num : nums) {
        b2 ^= b1 & num;
        b1 ^= num;
        mask = ~(b1 & b2); // k =3 =(11)_2
        b2 &= mask;
        b1 &= mask;
    }
    return b1 | b2;
}

还有种方法设计mod 3计数器：用数电知识，画出x1,x2,nums[i]的卡诺图真值表、化简x1,x2表达式。只是该方法泛化能力差，计数器位数多了以后表达式复杂。

其他数出现2次，两个数出现1次，求这两个数

• https://leetcode.com/problems/single-number-iii/

vector<int> singleNumber(vector<int>& nums) {
    // 设x和y是数组中只出现1次的两个数
    int xXorY = 0;
    for (auto num : nums) {
        xXorY ^= num;
    }
    // xXorY中任意一位1表示x和y该处不同，不妨取最后一位1来区分x和y
    int lastOne = xXorY & -xXorY;
    int x = 0;
    for (auto num : nums) {
        if (num & lastOne) x ^= num;
    }
    int y = x ^ xXorY;

    return {x, y};
}

有序数组中其他数出现两次、某个数出现一次，求这单个数

• https://leetcode.com/problems/single-element-in-a-sorted-array/

int singleNonDuplicate(vector<int>& nums) {
    // 由题知N是奇数，对于[0..N-2]的一对对，找第一对nums[m]!=nums[m^1]
    // nums[m]!=nums[m^1]作二分搜索条件满足[0 ... 0 1 1 ...]形式
    int l = -1, u = (int)nums.size() - 1;
    while (l + 1 < u) {
        int mid = l + (u - l) / 2;
        if (nums[mid] != nums[mid ^ 1]) u = mid;
        else l = mid;
    }
    return nums[u];
}