给定一个大小为 n 的整数数组，找出其中所有出现超过 ⌊ n/3 ⌋ 次的元素。
进阶：尝试设计时间复杂度为 O(n)、空间复杂度为 O(1)的算法解决此问题。
示例 1：
输入：[3,2,3] 输出：[3]
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/majority-element-ii 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
class Solution {
public List<Integer> majorityElement(int[] nums) {
List<Integer> ans = new ArrayList<>();
int a = nums[0];
int b = a;
int countA = 0;
int countB = 0;
for (int num : nums) {
if (num == a) {
countA++;
continue;
}
if (num == b) {
countB++;
continue;
}
if (countA == 0) {
a = num;
countA = 1;
continue;
}
if (countB == 0) {
b = num;
countB = 1;
continue;
}
countA--;
countB--;
}
countA = 0;
countB = 0;
for (int num : nums) {
if (num == a) {
countA++;
}
if (num == b) {
countB++;
}
}
if (countA > nums.length / 3) {
ans.add(a);
}
if (a != b && countB > nums.length / 3) {
ans.add(b);
}
return ans;
}
}
摩尔投票，两两抵抗
给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 个最小元素（从 1 开始计数）。
class Solution {
public int kthSmallest(TreeNode root, int k) {
Deque<TreeNode> stack = new LinkedList<>();
while (true) {
while (root != null) {
stack.push(root);
root = root.left;
}
root = stack.pop();
k--;
if (k == 0) {
return root.val;
}
root = root.right;
}
}
}
二叉搜索树的中序遍历是递增序列，每次进行比对K即可。
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
class Solution {
TreeNode ans;
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
dfs(root, p, q);
return ans;
}
public boolean dfs(TreeNode root, TreeNode p, TreeNode q) {
if (root == null) {
return false;
}
// 左子树是否含有 p 或 q
boolean l = dfs(root.left, p, q);
// 右子树是否含有 p 或 q
boolean r = dfs(root.right, p, q);
if ((l && r) || ((l || r) && (root == p || root == q))) {
ans = root;
}
return l || r || (root == p || root == q);
}
}