思路：
题目的主要信息：
- 一个长度为n的正整数数组，从中选取长度大于等于k的连续子序列
- “中数”为最大的整数x，使得序列中至少一半的数字大于等于x
- 求所有选出来的子序列中最大中数
方法一：暴力构造+优先队列
具体做法：
我们遍历两遍数组，找到每个不小于k的子序列的两个端点坐标。从一个端点遍历到另一个端点，利用优先队列（默认大根堆）记录这个子序列，然后先弹出队列总数一半少一个的元素（这里的一半要分奇偶讨论），下一个数就是我们要的中数。然后比较每次每个子序列的中数，找到最大值。
class Solution {
public:
int solve(int n, int k, vector<int>& a) {
int res = 0;
for(int i = 0; i < n; i++){
for(int j = i + k - 1; j < n; j++){ //构造所有长度
priority_queue<int> pq;
for(int k = i; k <= j; k++) //优先队列存这么个长度的所有子序列
pq.push(a[k]);
int m = 0;
if(pq.size() % 2) //奇数
m = pq.size() / 2 + 1;
else //偶数
m = pq.size() / 2;
while(--m) //先弹出一半少一个大于x的
pq.pop();
res = max(res, pq.top()); //弹出x
pq.top();
}
}
return res;
}
};复杂度分析：
- 时间复杂度：
，外面两层遍历，第一层遍历数组a，第二层最坏遍历
个数，中间遍历子序列最坏为
，其中每次加入优先队列一个元素需要
，最后弹出优先队列还是
，省去第次幂结果就是上述。
- 空间复杂度：
个
方法二：二分法
具体做法：
我们可以对原数组备份，然后进行排序，这样我们要找的最大中数一定在最大值到最小值之间。于是我们可以对排序后的数组进行二分查找，找到符合不小于k子序列的中数，又是最大值，即最后一个符合条件的中数。
我们用judge函数判断一个数num是否是符合条件的中数。我们记录数组a中不小于num的元素的位置，然后研究这些位置出现次数大于时，其首尾的长度即可。
class Solution {
public:
//判断数num是否是子序列长度不小于k的中数
bool judge(vector<int>& a, int num, int k){
vector<int> v;
for(int i = 0; i < a.size(); i++)
if(a[i] >= num)
v.push_back(i); //记录不小于num的元素的位置
int m = 0;
if(k % 2) //奇数情况
m = k / 2 + 1;
else //偶数情况
m = k / 2;
//i到j表示出现次数多于m个 研究第i个与第j个之间的位置
for(int i = 0; i < v.size(); i++)
for(int j = i + m - 1; j < v.size(); j++)
if((v[j] - v[i] + 1) <= (j - i + 1) * 2) //若是区间内满足出现二分之一以上
return true;
return false;
}
int solve(int n, int k, vector<int>& a) {
vector<int> temp = a;
sort(temp.begin(), temp.end());//递增排序
int left = 0, right = n - 1;
//最大的中数一定大于等于temp[0] 小于等于temp[n-1]
while(left <= right){ //二分法
int mid = (left + right) / 2; //每次找中间值
if(judge(a, temp[mid], k)) //如果满足大于等于k子序列的中数，收缩左边界
left = mid + 1;
else
right = mid - 1;
}
return temp[left - 1];
}
};复杂度分析：
- 时间复杂度：
，sort函数排序为
，二分法为序列长度对数级运算即
，经整合去除第次幂后如上
- 空间复杂度：
京公网安备 11010502036488号