資料結構
網路
關係型資料庫管理系統
作業系統
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 次瀏覽
