Given an integer array of size n, find all elements that appear more than
⌊ n/3 ⌋ times. The algorithm should run in linear time and in O(1) space.
Hint:
- How many majority elements could it possibly have?
注意for loop里的判断
class Solution {
public:
vector<int> majorityElement(vector<int>& nums) {
vector<int> rt;
if (nums.size() == 0) return rt;
int num1 = 0, num2 = 0, count1 = 0, count2 = 0;
for (int i = 0; i < nums.size(); i++) {
if (count1 == 0 && (count2 == 0 || nums[i] != num2)) {
num1 = nums[i];
count1++;
}else if (count2 == 0 && nums[i] != num1){
count2++;
num2 = nums[i];
}else if (nums[i] == num1) {
count1++;
}else if (nums[i] == num2) {
count2++;
}else {
count1--;
count2--;
}
}
count1 = 0;
count2 = 0;
for (int i = 0; i < nums.size(); i++) {
if (nums[i] == num1) count1++;
else if (nums[i] == num2) count2++;
}
if (count1 * 3 > nums.size()) rt.push_back(num1);
if (count2 * 3 > nums.size()) rt.push_back(num2);
return rt;
}
};
Kth Smallest Element in a BST
Given a binary search tree, write a function
kthSmallest to find the kth smallest element in it.
Note:
You may assume k is always valid, 1 ≤ k ≤ BST's total elements.
You may assume k is always valid, 1 ≤ k ≤ BST's total elements.
Follow up:
What if the BST is modified (insert/delete operations) often and you need to find the kth smallest frequently? How would you optimize the kthSmallest routine?
-------------------------------------------------------------------------------What if the BST is modified (insert/delete operations) often and you need to find the kth smallest frequently? How would you optimize the kthSmallest routine?
COME BACK for the follow up
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
void preorder(TreeNode* root, int &k, TreeNode *&kth) {
if (root == NULL) return;
preorder(root->left,k,kth);
k--;
if (k == 0) kth = root;
else preorder(root->right,k,kth);
}
int kthSmallest(TreeNode* root, int k) {
TreeNode *kth = NULL;
preorder(root,k,kth);
return kth->val;
}
};
另一种做法，找出子树的数量 updated on Jan-4th-2019
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
private TreeNode rt = null;
public int kthSmallest(TreeNode root, int k) {
dfs(root, k);
return rt.val;
}
private int dfs(TreeNode root, int k) {
if (root == null) return 0;
int l = dfs(root.left, k);
if (l + 1 == k) {
rt = root;
}
int r = dfs(root.right, k - l - 1);
return l + r + 1;
}
}
Follow up
修改TreeNode结构，加入count。O(n)重建树，O(lg n) 找到Kth smallest
