预习一下
lower_bound 的用法与写法
lower_bound 功能：在连续递增的数组中返回一个下标
i，其对应的数为 x。给定目标值
t，x 是第一个满足 t <= x
的数。
例如，下面的序列中，当 t = 2 时，lower_bound 返回的
i 为 2。
写法
灵茶山艾府提供了一版“开区间” lower_bound
的写法，记忆点：
- 初始端点都取不到，
l = -1, r = n。
while 里 l + 1 < r- 防止溢出，
mid = l + (r - l) / 2。
if 和 else 更新 l 和
r 时都不需要加 1 或减 1。
1
2
3
4
5
6
7
8
9
| int lower_bound(int t) {
int l = -1, r = n;
while(l + 1 < r) {
int mid = l + (r - l) / 2;
if (a[mid] >= t) r = mid;
else l = mid;
}
return l;
}
|
记不住也可以使用 C++ 的 STL：
1
| lower_bound(nums.begin(), nums.end(), t);
|
用法
本质上所有对区间的求解都可以使用 lower_bound 替代：
- 求
t <= x，为 lower_bound(t)。
- 求
t < x，为
lower_bound(t + 1)，求第一个大于 t 的数。
- 求
x < t，为
lower_bound(t) - 1，求第一个大于等于 t
的数，下标再减 1。
- 求
x <= t，为
lower_bound(t + 1) - 1，求第一个大于等于 t + 1
的数，下标再减 1。
给你一个按照非递减顺序排列的整数数组 nums，和一个目标值
target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回
[-1, -1]。
你必须设计并实现时间复杂度为 O(log n)
的算法解决此问题。
示例 1：
1
2
| 输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]
|
示例 2：
1
2
| 输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]
|
示例 3：
1
2
| 输入：nums = [], target = 0
输出：[-1,-1]
|
提示：
-
0 <= nums.length <= 105
-
-109 <= nums[i] <= 109
-
nums 是一个非递减数组
-
-109 <= target <= 109
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
public:
vector<int> searchRange(vector<int>& nums, int t) {
auto lx = lower_bound(nums.begin(), nums.end(), t);
if (lx == nums.end() || *lx != t) {
return vector<int>{-1, -1};
}
auto rx = lower_bound(nums.begin(), nums.end(), t + 1) - 1;
return vector<int>{
static_cast<int>(lx - nums.begin()),
static_cast<int>(rx - nums.begin())
};
}
};
|
题解：
t 元素第一个出现位置，即为第一个满足
t <= x 的数，可用 lower_bound(t)
直接求解。
t 元素最后一个出现位置，即为第一个满足
t + 1 <= x 的数的下标减 1，转变思路，可用
lower_bound(t + 1) - 1 直接求解。
示例 1:
1
2
| 输入: nums = [1,3,5,6], target = 5
输出: 2
|
示例 2:
1
2
| 输入: nums = [1,3,5,6], target = 2
输出: 1
|
示例 3:
1
2
| 输入: nums = [1,3,5,6], target = 7
输出: 4
|
1
2
3
4
5
6
7
8
9
10
| class Solution {
public:
int searchInsert(vector<int>& nums, int t) {
auto it = lower_bound(nums.begin(), nums.end(), t);
if (it == nums.end()) {
return nums.size();
}
return static_cast<int>(it - nums.begin());
}
};
|
题解：
仅需要特别处理一下该元素不存在，且 it
指针位于数组末尾的情况，此时插入的位置应该为数组的末尾。其余情况均为
lower_bound(t) 的解。
示例 1：
1
2
3
| 输入：nums = [-2,-1,-1,1,2,3]
输出：3
解释：共有 3 个正整数和 3 个负整数。计数得到的最大值是 3 。
|
示例 2：
1
2
3
| 输入：nums = [-3,-2,-1,0,0,1,2]
输出：3
解释：共有 2 个正整数和 3 个负整数。计数得到的最大值是 3 。
|
示例 3：
1
2
3
| 输入：nums = [5,20,66,1314]
输出：4
解释：共有 4 个正整数和 0 个负整数。计数得到的最大值是 4 。
|
1
2
3
4
5
6
7
8
| class Solution {
public:
int maximumCount(vector<int>& nums) {
auto lx = lower_bound(nums.begin(), nums.end(), 0);
auto rx = lower_bound(nums.begin(), nums.end(), 1);
return max(lx - nums.begin(), nums.end() - rx);
}
};
|
题解：
对于负整数，需要通过 lower_bound 找到第一个大于等于 0
的数，即 lower_bound(0)。负整数的数量为第一个大于等于
0 的数的下标。
对于正整数，需要找到最后一个大于 0 的数，可以转换成大于等于
1 的数，即
lower_bound(1)。正整数的数量为数组长度减去该数的下标。
得到两个结果取最大值，求得答案。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| class SnapshotArray {
public:
unordered_map<int, vector<pair<int, int>>> array;
int snapshot_call = 0;
SnapshotArray(int length) {
for (int i = 0; i < length; i++) {
array[i].push_back({0, 0});
}
}
void set(int index, int val) {
array[index].push_back({snapshot_call, val});
}
int snap() {
int rt = snapshot_call;
snapshot_call += 1;
return rt;
}
int get(int index, int snap_id) {
vector<pair<int, int>>& nums = array[index];
int l = -1, r = nums.size();
while (l + 1 < r) {
int mid = l + (r - l) / 2;
if (nums[mid].first >= snap_id + 1) r = mid;
else l = mid;
}
return nums[r - 1].second;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
| class SnapshotArray {
public:
unordered_map<int, vector<pair<int, int>>> array;
int snapshot_call = 0;
SnapshotArray(int length) {
for (int i = 0; i < length; i++) {
array[i].push_back({0, 0});
}
}
void set(int index, int val) {
array[index].push_back({snapshot_call, val});
}
int snap() {
int rt = snapshot_call;
snapshot_call += 1;
return rt;
}
int get(int index, int snap_id) {
const vector<pair<int, int>>& nums = array[index];
auto it = lower_bound(
nums.begin(),
nums.end(),
make_pair(snap_id + 1, 0),
[](const pair<int, int>& a, const pair<int, int>& b) {
return a.first < b.first;
});
return prev(it)->second;
}
};
|
题解：
我们需要记录每一个 index 对应下标的更新记录，使用
pair<int, int>，first 为
snap_id，second 为 value。
在 get 操作传入时，通过传入的 snap_id
对其二分搜索，目标是找到该 snap_id 的最后一个
value。即查找 lower_bound(snap_id + 1)
再下标减 1。
输入：
1
2
3
4
| ["TopVotedCandidate", "q", "q", "q", "q", "q", "q"]
persons = [0, 1, 1, 0, 0, 1, 0]
times = [0, 5, 10, 15, 20, 25, 30]
qs = [3], [12], [25], [15], [24], [8]
|
输出：
1
| [null, 0, 1, 1, 0, 0, 1]
|
解释：
1
2
3
4
5
6
7
| TopVotedCandidate topVotedCandidate = new TopVotedCandidate([0, 1, 1, 0, 0, 1, 0], [0, 5, 10, 15, 20, 25, 30]);
topVotedCandidate.q(3); // 返回 0 ，在时刻 3 ，票数分布为 [0] ，编号为 0 的候选人领先。
topVotedCandidate.q(12); // 返回 1 ，在时刻 12 ，票数分布为 [0,1,1] ，编号为 1 的候选人领先。
topVotedCandidate.q(25); // 返回 1 ，在时刻 25 ，票数分布为 [0,1,1,0,0,1] ，编号为 1 的候选人领先。（在平局的情况下，1 是最近获得投票的候选人）。
topVotedCandidate.q(15); // 返回 0
topVotedCandidate.q(24); // 返回 0
topVotedCandidate.q(8); // 返回 1
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| class TopVotedCandidate {
public:
vector<int> win_time;
vector<int> winner;
TopVotedCandidate(vector<int>& persons, vector<int>& times) {
unordered_map<int, int> votes;
int win_votes = 0;
int win_person = 0;
for (int i = 0; i < times.size(); i ++) {
votes[persons[i]] += 1;
if (win_time.empty() || votes[persons[i]] >= win_votes) {
win_votes = votes[persons[i]];
win_person = persons[i];
win_time.push_back(times[i]);
winner.push_back(persons[i]);
} else {
win_time.push_back(times[i]);
winner.push_back(win_person);
}
}
}
int q(int t) {
auto it = lower_bound(win_time.begin(), win_time.end(), t + 1) - 1;
return winner[it - win_time.begin()];
}
};
|
题解：
预先持久化每一个时间节点上的胜者，查询时通过 t
二分查询，找到最后一个小于等于 t
的时间节点上的胜者。例如：
- 当
t = 24 时，应该找到的是 20 而不是
25。
- 当
t = 25 时，应该找到的是 25
资料
