请给出一个logn的做法
时间: 2024-06-05 15:08:24 浏览: 12
给定一个有序数组和一个目标数字,找到目标数字在数组中的位置。一个 logn 的解决方案是使用二分查找。具体来说,首先找到中间元素,如果目标数字等于中间元素,则返回其索引;如果目标数字小于中间元素,则在数组的左半部分重复这个过程;如果目标数字大于中间元素,则在数组的右半部分重复这个过程,直到找到目标数字或者确定目标数字不在数组中。
相关问题
c++给定一个长度为 n 的序列 {an},求其最长上升子序列长度。O(n logn)
可以使用二分查找和动态规划的思想,时间复杂度为 O(n logn)。
具体的做法是,维护一个数组 dp,dp[i] 表示长度为 i 的最长上升子序列的末尾元素的最小值。初始时,dp[1] = a[1],其余为 INF。然后从 i = 2 到 n,对于每个 a[i],在 dp 数组中查找第一个大于等于 a[i] 的元素 dp[j],将其替换为 a[i]。如果不存在这样的元素,说明 a[i] 大于所有的 dp[j],此时应该将 dp 数组的长度加 1,即 dp[len+1] = a[i],其中 len 表示当前 dp 数组的最大下标。最终,dp 数组的长度就是最长上升子序列的长度。
代码如下:
```c++
const int INF = 0x3f3f3f3f;
int dp[N], len = 1; // dp 数组和最大下标 len
dp[1] = a[1];
for (int i = 2; i <= n; ++i) {
if (a[i] > dp[len]) { // 情况 1
dp[++len] = a[i];
} else { // 情况 2
int pos = lower_bound(dp + 1, dp + len + 1, a[i]) - dp;
dp[pos] = a[i];
}
}
```
其中 lower_bound 函数可以使用 STL 中的 lower_bound,也可以手写实现。
c++ 初始为0,每次操作对一个区间加一,每次操作时要实时输出最大和最小的差,O(logn)解法
这是一道数据结构题,可以使用线段树来解决。具体做法是,根据区间加一的操作,在线段树上进行一次区间修改,同时记录每个节点表示的区间内的最大值和最小值,更新时可以直接从左右子节点获取信息,时间复杂度为O(logn)。同时,由于线段树的深度为logn,所以在查询最大最小差值时也可以直接在线段树上计算。