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

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

给你一个非空整数数组 nums , 除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/single-number

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

LeetCode136_XOR

	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 为当前读入的值。代码如下：

LeetCode169_BoyerMooreVoting

	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;
	}
	};

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

# LeetCode 169. 多数元素

栈

多维数据库