一些不成体系的算法杂题记录。

# LeetCode 136. 只出现一次的数字

给你一个非空整数数组 nums , 除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/single-number

采用异或的性质可解。注意异或运算具有交换律、结合律。且 $a\oplus a = 0$.

class Solution {

public:

    int singleNumber(vector<int>& nums) {

        int num = 0;

        for(auto n:nums) num = num ^ n;

        return num;

    }

};

# LeetCode 169. 多数元素

给定一个大小为 n 的数组  nums , 返回其中的多数元素。多数元素是指在数组中出现次数 大于  ⌊n/2⌋  的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/majority-element

如果将时间复杂度限制在 $O(n\log n)$, 空间复杂度限制在 $O(1)$, 那么可以采用的方式包括但不限于排序、分治。如果将时间、空间复杂度均限制在 $O(n)$, 那么可以采用哈希实现。此外，还可以采用随机化算法应对卡常情况。

但如果将时间复杂度限制为 $O(n)$, 空间复杂度限制为 $O(1)$, 那么可以采用的方法为 Boyer-Moore 投票法。算法的思路为：维护一个候选众数 candidate 和一个计数器 count . 依次读取数组中元素的过程中，若当前读取的元素与 candidate 相同，则 count++ , 否则 count-- . 当 count==0 时，更换 candidate 为当前读入的值。代码如下：

class Solution {

public:

    int majorityElement(vector<int>& nums) {

        int candidate = 0;

        int count = 0;

        for (auto num:nums) {

            if (count==0) candidate=num;

            count += (candidate==num) ? 1 : (-1);

        }

        return candidate;

    }

};