数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律学查找给定配对中平均值略大的配对的索引
在这个问题中，我们将为每对找到索引值，使得结果对的平均值刚好大于当前对的平均值。
为了解决这个问题，我们将使用排序算法和二分查找技术。我们将使用排序算法根据对的平均值对数组进行排序，并使用二分查找算法从排序后的数组中搜索平均值更大的对。
问题陈述
我们给定了一个包含 N 对正整数的 pairs[] 数组。还给定每个对的第一个元素是不同的。我们需要找到每个对的索引值，其平均值刚好大于当前对的平均值。
{a, b} 的平均值为 floor((a + b)/2)。
示例
Input – pairs = {{1, 5}, {2, 3}, {3, 6}}
Output – 2 0 -1
解释
{3, 6} 的平均值刚好大于 {1, 5} 对的平均值。因此，它打印索引 2。
{2, 3} 的平均值为 2，而 {1, 5} 的平均值为 3。因此，它打印索引 0。
不存在任何平均值大于 {3, 6} 对的平均值的配对。因此，它打印 -1。
Input – pairs = {{3, 2}, {2, 8}, {4, 6}, {1, 11}}
Output – 2 3 3 -1
解释
对于多个对，相同的索引值也可能是答案。
Input – pairs = {{1, 5}, {2, 4}, {3, 3}, {4, 2}};
Output – -1 -1 -1 -1
解释
当所有索引的平均值都相同时，它为每个索引打印 -1。
方法 1
在这种方法中，我们将使用 sort() 方法和比较器根据对的平均值对给定的对列表进行排序。之后，我们将对每个对使用二分查找来搜索平均值刚好大于当前对的平均值的配对的索引。
算法
步骤 1 - 定义 'indices' 映射以存储每个对的实际索引。
步骤 2 - 遍历给定的对列表并将索引映射到对的第一个元素，因为每个对的第一个元素是唯一的。
步骤 3 - 使用 sort() 方法对列表进行排序，并将 pairCompare() 函数作为第三个参数传递。pairComapre() 函数是一个比较器函数，如果第一对的平均值小于或等于第二对的平均值，则返回 true。否则，它返回 false。
步骤 4 - 接下来，初始化 'output' 列表以存储答案并开始遍历排序后的对列表。
步骤 5 - 获取当前对的平均值，并将其作为 getLowerBound() 函数的参数传递，以获取平均值刚好更大的对。
步骤 5.1 - 在 getLowerBound() 函数中，初始化二分查找的左指针和右指针，以及 'ind' 为 -1 以存储所需对的索引值。
步骤 5.2 - 进行遍历，直到左指针小于或等于右指针。获取中间索引以及位于中间索引处的对的平均值。
步骤 5.3 - 如果中间索引处的平均值小于目标平均值，则将 left 更新为 middle + 1。否则，将 right 更新为 middle – 1 并将 'ind' 更新为中间索引。
步骤 5.4 - 当循环迭代完成后，如果 'ind' 值为 -1，则返回 -1。
步骤 5.5 - 获取位于 'ind' 索引处的对的平均值。如果平均值大于目标平均值，则返回 'ind' 值。否则，返回 -1。
步骤 6 - 如果 getLowerBound() 返回 -1，则使用 -1 更新输出列表中当前对的实际索引，我们可以从 indices 映射中获取该索引。否则，使用结果索引值更新输出列表。
示例
#include <bits/stdc++.h>
using namespace std;
int getLowerBound(vector<pair<int, int>> pairs, int t_avg) {
// Variables for binary search
int left = 0, right = (int)pairs.size() - 1;
int ind = -1;
// Binary search algorithm
while (left <= right) {
// Get middle index
int middle = (left + right) / 2;
// Get the average of the middle index
int avg = (pairs[middle].first + pairs[middle].second) / 2;
// When the average is smaller than the target average
if (avg <= t_avg)
left = middle + 1;
else {
// When the average is larger than the target average
right = middle - 1;
ind = middle;
}
}
if (ind == -1)
return -1;
// Take average of last found index
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;
// Sort based on the average value
return first <= second;
}
void getPairs(vector<pair<int, int>> &pairs, int len) {
// To track indices and their average
unordered_map<int, int> indices;
// Map the first element of the pair and the current index
for (int p = 0; p < len; p++) {
indices[pairs[p].first] = p;
}
// Sort list based on the condition of comparators
sort(pairs.begin(), pairs.end(), pairCompare);
// To store output
vector<int> output(len);
for (int p = 0; p < len; p++) {
// Get the average of the pair
int avg = (pairs[p].first + pairs[p].second) / 2;
// Get lower bound of pair
int ind_val = getLowerBound(pairs, avg);
// If the current pair has the largest average value
if (ind_val == -1)
output[indices[pairs[p].first]] = -1;
// When we find the valid pair having just a greater average value than the current value
else
output[indices[pairs[p].first]] = indices[pairs[ind_val].first];
}
// Print the final array
for (auto x : output)
cout << x << ' ';
}
int main() {
vector<pair<int, int>> pairs = {{1, 5}, {2, 3}, {3, 6}};
int pairs_len = pairs.size();
cout << "The indices according to the given condition are ";
getPairs(pairs, pairs_len);
return 0;
}
输出
The indices according to the given condition are 2 0 -1
时间复杂度 - O(N*logN + logN)，其中 O(NlogN) 用于排序列表，O(logN) 用于搜索索引值。
空间复杂度 - O(N) 用于存储答案值。
我们使用二分查找算法来搜索平均值刚好更大的索引。但是，程序员可以使用线性搜索算法，因为在大多数情况下，平均值刚好更大的对将位于当前对的旁边。
67 次浏览
