在给定的对中找出平均值刚好大于当前对的对的索引
在这个问题中，我们将找到每对的索引值，使得结果对的平均值刚好大于当前对的平均值。
为了解决这个问题，我们将使用排序算法和二分搜索技术。我们将使用排序算法根据对的平均值对数组进行排序，并使用二分搜索算法从排序后的数组中搜索平均值较大的对。
问题陈述
我们给出了一个包含 N 对正整数的对的pairs[]数组。还给出了每对的第一个元素是不同的。我们需要找到每个平均值刚好大于当前对的对的索引值。
{a, b} 的平均值是 floor((a + b)/2)。
示例
输入 – 对 = {{1, 5}, {2, 3}, {3, 6}}
输出 – 2 0 -1
解释
{3, 6} 的平均值刚好大于 {1, 5} 对的平均值。因此，它打印索引 2。
{2, 3} 的平均值是 2，而 {1, 5} 的平均值是 3。因此，它打印索引 0。
不存在任何一对的平均值大于 {3, 6} 对的平均值。因此，它打印 -1。
输入 – 对 = {{3, 2}, {2, 8}, {4, 6}, {1, 11}}
输出 – 2 3 3 -1
解释
也可能相同的索引值可以是多个对的答案。
输入 – 对 = {{1, 5}, {2, 4}, {3, 3}, {4, 2}};
输出 – -1 -1 -1 -1
解释
当所有索引的平均值相同时，它会为每个索引打印 -1。
方法 1
在这种方法中，我们将使用 sort() 方法和比较器根据对的平均值对给定的对列表进行排序。之后，我们将对每对使用二分搜索来搜索平均值刚好大于当前对平均值的对的索引。
算法
步骤 1 - 定义"索引"映射以存储每对的实际索引。
步骤 2 - 遍历给定的对列表并将索引映射到对的第一个元素，因为每对的第一个元素都是唯一的。
步骤 3 - 使用 sort() 方法对列表进行排序，并将 pairCompare() 函数作为第三个参数传递。pairComapre() 函数是一个比较器函数，如果第一对的平均值小于或等于第二对的平均值，则返回 true。否则，返回 false。
步骤 4 − 接下来，初始化"输出"列表以存储答案，并开始遍历已排序的对列表。
步骤 5 − 取当前对的平均值，并将其作为 getLowerBound() 函数的参数传递，以获取平均值较大的对。
步骤 5.1 − 在 getLowerBound() 函数中，初始化二分搜索的左指针和右指针，并使用 -1 初始化"ind"以存储所需对的索引值。
步骤 5.2 − 进行遍历，直到左指针小于或等于右指针。取中间索引和位于中间索引处的对的平均值。
步骤 5.3 - 如果中间索引处的平均值小于目标平均值，则用中间 + 1 更新左侧。否则，用中间 - 1 更新右侧，用中间索引更新"ind"。
步骤 5.4 - 循环迭代完成后，如果"ind"值为 -1，则返回 -1。
步骤 5.5 - 取位于"ind"索引处的对的平均值。如果平均值大于目标平均值，则返回"ind"值。否则，返回 -1。
步骤 6 - 如果 getLowerBound() 返回 -1，则使用 -1 更新当前对的实际索引处的输出列表，我们可以从索引图中获取该索引。否则，使用结果索引值更新输出列表。
示例
#include <bits/stdc++.h>
using namespace std;
int getLowerBound(vector<pair<int, int>> pairs, int t_avg) {
// 二分查找的变量
int left = 0, right = (int)pairs.size() - 1;
int ind = -1;
// 二分查找算法
while (left <= right) {
// 获取中间索引
int middle = (left + right) / 2;
// 获取中间索引的平均值
int avg = (pairs[middle].first + pair[middle].second) / 2;
// 当平均值小于目标平均值时
if (avg <= t_avg)
left = middle + 1;
else {
// 当平均值大于目标平均值时
right = middle - 1;
ind = middle;
}
}
if (ind == -1)
return -1;
// 取最后找到的索引的平均值
int avg = (pairs[ind].first + pairs[ind].second) / 2;
if (avg > t_avg)
return ind;
return -1;
}
bool pairCompare(pair<int, int> &m, pair<int, int> &n) {
int first = (m.first + m.second) / 2;
int second = (n.first + n.second) / 2;
// 根据平均值排序
return first <= second;
}
void getPairs(vector<pair<int, int>> &pairs, int len) {
// 跟踪索引及其平均值
unordered_map<int, int> indices;
// 映射对的第一个元素和当前索引
for (int p = 0; p < len; p++) {
indices[pairs[p].first] = p;
}
// 根据比较器的条件对列表进行排序
sort(pairs.begin(), pair.end(), pairCompare);
// 存储输出
vector<int> output(len);
for (int p = 0; p < len; p++) {
// 获取对的平均值
int avg = (pairs[p].first + pair[p].second) / 2;
// 获取对的下限
int ind_val = getLowerBound(pairs, avg);
// 如果当前对具有最大平均值
if (ind_val == -1)
output[indices[pairs[p].first]] = -1;
// 当我们找到平均值刚好大于当前值的有效对时
else
output[indices[pairs[p].first]] = indices[pairs[ind_val].first];
}
// 打印最终数组
for (auto x : output)
cout << x << ' ';
}
int main() {
vector<pair<int, int>> pair = {{1, 5}, {2, 3}, {3, 6}};
int pair_len = pair.size();
cout << "根据给定条件的索引为 ";
getPairs(pairs, pair_len);
return 0;
}
输出
根据给定条件的索引为 2 0 -1
时间复杂度 − O(N*logN + logN)，其中 O(NlogN) 用于对列表进行排序，O(logN) 用于搜索索引值。
空间复杂度 − O(N) 用于存储答案值。
我们使用二分搜索算法来搜索平均值较大的索引。但是，程序员可能会使用线性搜索算法，因为在大多数情况下，平均值较大的对将位于当前对的旁边。
