如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。例如，[2,3,4] 的中位数是 3[2,3] 的中位数是 (2 + 3) / 2 = 2.5设计一个支持以下两种操作的数据结构：void addNum(int num) - 从数据流中添加一个整数到数据结构中。double findMedian() - 返回目前所有元素的中位数。思路：合适的数据结构是关键，使用一个有序数组，每次添加数据之后也是一个有序数组，这样，每次可以O(1)时间内读出中间数，添加数据的时间复杂度为O(n)。使用一个avl树，添加数据的时间复杂度为O(logN)。但是avl树实现起来比较复杂。考虑有序数组，中间数把数组分为两部分，左边部分的数都小于中间数，右边部分的数都大于中间数，至于左边部分的数是否有序不重要，右边也是。左边的数加上中间数，就是一个大根堆，右边的数加上中间数就是一个小根堆。用两个优先队列表示左右两边的数，那么添加数据的时间复杂度也是log(N),读取中间数的时间复

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。思路：数组中有一个数出现的次数超过数组长度的一半，设这个数为a，其他数为b、c、d...。设time[x]表示x出现的次数，则time[a] > time[b]+time[c]+time[d]+...。time[a]-(time[b]+time[c]+time[d]+...) > 0。time[a]-time[b]-time[c]-time[d]-... > 0。从左往右遍历数组，用一个变量表示当前数cur，一个变量表示当前数出现的次数time。当数组中出现和cur相同的数时，time加一，不同时，time减一。遍历完数组后，cur就是答案代码：class Solution { public: int majorityElement(vector<int>& nums) { int length = nums.size(); if(length == 0) { return 0; } int

输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。思路一：使用一个大小为k的大根堆，遍历数组arr，遇到比根小的，则更新堆。最后大根堆里的数就是最小的k个数。代码：class Solution { public: vector<int> getLeastNumbers(vector<int>& arr, int k) { int l = arr.size(); if (l < k || k <= 0) { return {}; } priority_queue<int> q; for(int i = 0;i < k;i++) { q.push(arr[i]); } for(int i = k;i < l;i++) { if (q.top() &g

输入一个字符串，打印出该字符串中字符的所有排列。你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。思路：记字符串的长度为n，则有n个位置，对于位置i，字符串里的每个字符都放一次，对于位置i+1，字符串除i位置的字符外，其他都放一次。当到达位置n时，则出现一个满足要求的答案。题目要求不能有重复元素，所以要去重。先把字符串排序，则相同的字符相邻。对于两个相同的字符，如果前一个使用过了，后面一个则不使用。即vis[j - 1] && s[j - 1] == s[j]代码:class Solution { public: vector<string> rec; vector<int> vis; void backtrack(const string& s, int i, int n, string& perm) { if (i == n) { rec.push_back(perm); return; } for

请实现两个函数，分别用来序列化和反序列化二叉树。你需要设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。思路：序列化比较简单就是深度优先遍历，前中后三种顺序都可以。反序列化时，从前往后读入字符，先遇到根节点，所以前序遍历比较合适。序列化时，null节点用$符号表示，节点与节点之间用,分割。反序列化时,先用,分割。然后一个节点一个节点处理。代码：class Solution { public: void rserialize(TreeNode* root, string& str) { if (root == nullptr) { str += "$,"; } else { str += to_string(root->val) + ","; rserialize(root->left, str