Dada una array de pares arr[] de tamaño N donde el primer valor de todos los pares es distinto. Para cada par de la array dada, encuentre el índice de otro par que tenga un promedio un poco mayor que este.
Nota: El promedio de dos números a y b se define como el piso ( a + b ) / 2.
Ejemplos:
Entrada: { {2, 3}, {1, 3}, {3, 4} }
Salida: { 2, 2, -1}
Explicación: El promedio de todos los elementos de par correspondientes son {2, 2, 3}Entrada: { {3, 5}, {1, 3}, {2, 4} }
Salida: { -1, 2, 0 }
Explicación: El promedio de todos los elementos de par correspondientes es {4, 2, 3}.
Entonces, para {1, 3} aunque {3, 5} tiene un promedio mayor pero
{2, 4} tiene un promedio apenas mayor que {1, 3} en la array dada.
Enfoque: este problema se puede resolver mediante la búsqueda binaria . Siga los pasos que se mencionan a continuación:
- Ordene la array de pares sobre la base de los valores promedio.
- Aplique la búsqueda binaria para cada elemento para encontrar el par que tenga un valor promedio apenas mayor que este.
- Para realizar un seguimiento de los índices, utilice un mapa hash o un mapa desordenado, ya que los primeros valores son distintos en todos los pares.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to implement above approach
#include <bits/stdc++.h>
using namespace std;
// Applying custom lower bound
// on average values
int lbound(vector<pair<int, int> >& arr,
int& target)
{
// Initializing low and high variables
int low = 0, high = (int)arr.size() - 1;
// ans keeps the track of desired index
int ans = -1;
// Applying binary search
while (low <= high) {
int mid = (low + high) / 2;
int avg = (arr[mid].first
+ arr[mid].second)
/ 2;
if (avg <= target)
low = mid + 1;
else {
high = mid - 1;
ans = mid;
}
}
if (ans == -1)
return -1;
// Return the ans
int avg = (arr[ans].first
+ arr[ans].second)
/ 2;
if (avg > target)
return ans;
return -1;
}
// Compare function
bool compare(pair<int, int>& a,
pair<int, int>& b)
{
int val1 = (a.first + a.second) / 2;
int val2 = (b.first + b.second) / 2;
return val1 <= val2;
}
// Function to find indices of desired pair
// for each element of the array of pairs
void findPair(vector<pair<int, int> >& arr,
int N)
{
// Declaring an unordered map
// to keep the track of
// indices since the order
// is going to be changed
unordered_map<int, int> lookUp;
// Iterating over the given vector
for (int i = 0; i < N; i++) {
lookUp[arr[i].first] = i;
}
// Sorting the given vector of pairs
// by passing a custom comparator
sort(arr.begin(), arr.end(), compare);
// Declaring ans vector to store
// the final answer
vector<int> ans(N);
for (int i = 0; i < N; i++) {
// Average value
int target = (arr[i].first
+ arr[i].second)
/ 2;
// Calling lbound() function
int ind = lbound(arr, target);
// If no such pair exists
if (ind == -1)
ans[lookUp[arr[i].first]] = -1;
// If such a pair exists
else
ans[lookUp[arr[i].first]]
= lookUp[arr[ind].first];
}
// Print the final array
for (auto x : ans)
cout << x << ' ';
}
// Driver code
int main()
{
// Initializing a vector of pairs
vector<pair<int, int> > arr
= { { 2, 3 }, { 1, 3 }, { 3, 4 } };
// Size of the vector
int N = arr.size();
findPair(arr, N);
return 0;
}
Java
import java.util.*;
import java.io.*;
// Java program for the above approach
class GFG{
static class pair {
int first, second;
public pair(int first, int second) {
this.first = first;
this.second = second;
}
}
static ArrayList<pair> arr;
static int target;
// Applying custom lower bound
// on average values
static int lbound()
{
// Initializing low and high variables
int low = 0, high = arr.size() - 1;
// ans keeps the track of desired index
int ans = -1;
// Applying binary search
while (low <= high) {
int mid = (low + high) / 2;
int a = (arr.get(mid).first + arr.get(mid).second) / 2;
if (a <= target)
low = mid + 1;
else {
high = mid - 1;
ans = mid;
}
}
if (ans == -1){
return -1;
}
// Return the ans
int avg = (arr.get(ans).first + arr.get(ans).second) / 2;
if (avg > target){
return ans;
}
return -1;
}
// Compare function
static class Comp implements Comparator<pair>{
public int compare(pair a, pair b){
return ((a.first + a.second) / 2)-((b.first + b.second) / 2);
}
}
// Function to find indices of desired pair
// for each element of the array of pairs
static void findPair(int N)
{
// Declaring an unordered map
// to keep the track of
// indices since the order
// is going to be changed
HashMap<Integer, Integer> lookUp = new HashMap<Integer, Integer>();
// Iterating over the given vector
for (int i = 0 ; i < N ; i++) {
lookUp.put(arr.get(i).first, i);
}
// Sorting the given vector of pairs
// by passing a custom comparator
Collections.sort(arr, new Comp());
// Declaring ans vector to store
// the readonly answer
ArrayList<Integer> ans = new ArrayList<Integer>();
for (int i = 0 ; i < N ; i++) {
ans.add(0);
// Average value
target = (arr.get(i).first + arr.get(i).second) / 2;
// Calling lbound() function
int ind = lbound();
// If no such pair exists
if (ind == -1)
ans.set(lookUp.get(arr.get(i).first), -1);
// If such a pair exists
else
ans.set(lookUp.get(arr.get(i).first), lookUp.get(arr.get(ind).first));
}
// Print the readonly array
for (int i = 0 ; i < ans.size() ; i++){
System.out.print(ans.get(i) + " ");
}
System.out.println("");
}
public static void main(String args[])
{
// Initializing a vector of pairs
arr = new ArrayList<pair>();
arr.add(new pair(2, 3));
arr.add(new pair(1, 3));
arr.add(new pair(3, 4));
// Size of the vector
int N = arr.size();
findPair(3);
}
}
// This code is contributed by subhamgoyal2014.
Python3
# Python3 code for the above approach
# Applying custom lower bound
# on average values
from functools import cmp_to_key
def mycmp(a, b):
val1 = (a['first'] + a['second']) // 2
val2 = (b['first'] + b['second']) // 2
return val1 - val2
def lbound(arr, target):
# Initializing low and high variables
low,high = 0,len(arr) - 1
# ans keeps the track of desired index
ans = -1
# Applying binary search
while (low <= high):
mid = (low + high) // 2
avg = (arr[mid]['first'] + arr[mid]['second'])// 2
if (avg <= target):
low = mid + 1
else:
high = mid - 1
ans = mid
if (ans == -1):
return -1
# Return the ans
avg = (arr[ans]['first'] + arr[ans]['second'])// 2
if (avg > target):
return ans
return -1
# Function to find indices of desired pair
# for each element of the array of pairs
def findPair(arr, N):
# Declaring an unordered map
# to keep the track of
# indices since the order
# is going to be changed
lookUp = [0 for i in range(1000001)]
# Iterating over the given vector
for i in range(N):
lookUp[arr[i]['first']] = i
# Sorting the given vector of pairs
# by passing a custom comparator
arr.sort(key = cmp_to_key(mycmp))
# Declaring ans vector to store
# the final answer
ans = [0 for i in range(N)]
for i in range(N):
# Average value
target = (arr[i]['first'] + arr[i]['second']) // 2
# Calling lbound() function
ind = lbound(arr, target)
# If no such pair exists
if (ind == -1):
ans[lookUp[arr[i]['first']]] = -1
# If such a pair exists
else:
ans[lookUp[arr[i]['first']]] = lookUp[arr[ind]['first']]
# Print the final array
for x in ans:
print(x ,end = ' ')
# Driver code
# Initializing a list of pairs
arr = [{ 'first': 2, 'second': 3 }, { 'first': 1, 'second': 3 }, { 'first': 3, 'second': 4 }]
# Size of the vector
N = len(arr)
findPair(arr, N)
# This code is contributed by Shinjanpatra
C#
// C# program to implement above approach
using System;
using System.Linq;
using System.Collections.Generic;
public class GFG {
public class pair {
public int first, second;
public pair(int first, int second) {
this.first = first;
this.second = second;
}
}
static List<pair> arr;
static int target;
// Applying custom lower bound
// on average values
static int lbound()
{
// Initializing low and high variables
int low = 0, high = arr.Count - 1;
// ans keeps the track of desired index
int ans = -1;
// Applying binary search
while (low <= high) {
int mid = (low + high) / 2;
int a = (arr[mid].first + arr[mid].second) / 2;
if (a <= target)
low = mid + 1;
else {
high = mid - 1;
ans = mid;
}
}
if (ans == -1)
return -1;
// Return the ans
int avg = (arr[ans].first + arr[ans].second) / 2;
if (avg > target)
return ans;
return -1;
}
// Compare function
// Function to find indices of desired pair
// for each element of the array of pairs
static void findPair(int N)
{
// Declaring an unordered map
// to keep the track of
// indices since the order
// is going to be changed
Dictionary<int,int> lookUp = new Dictionary<int,int>();
// Iterating over the given vector
for (int i = 0; i < N; i++) {
lookUp[arr[i].first] = i;
}
// Sorting the given vector of pairs
// by passing a custom comparator
arr.Sort((a, b) => ((a.first + a.second) / 2)-((b.first + b.second) / 2));
// Declaring ans vector to store
// the readonly answer
List<int> ans = new List<int>();
for (int i = 0; i < N; i++) {
ans.Add(0);
// Average value
target = (arr[i].first
+ arr[i].second)
/ 2;
// Calling lbound() function
int ind = lbound();
// If no such pair exists
if (ind == -1)
ans[lookUp[arr[i].first]] = -1;
// If such a pair exists
else
ans[lookUp[arr[i].first]]
= lookUp[arr[ind].first];
}
// Print the readonly array
foreach ( int x in ans)
Console.Write(x + " ");
}
// Driver code
public static void Main(String[] args)
{
// Initializing a vector of pairs
arr = new List<pair>();
arr.Add( new pair(2, 3));
arr.Add(new pair(1, 3));
arr.Add(new pair(3, 4));
// Size of the vector
int N = arr.Count;
findPair(3);
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// JavaScript code for the above approach
// Applying custom lower bound
// on average values
function lbound(arr, target)
{
// Initializing low and high variables
let low = 0, high = arr.length - 1;
// ans keeps the track of desired index
let ans = -1;
// Applying binary search
while (low <= high) {
let mid = Math.floor((low + high) / 2);
let avg = Math.floor((arr[mid].first
+ arr[mid].second)
/ 2);
if (avg <= target)
low = mid + 1;
else {
high = mid - 1;
ans = mid;
}
}
if (ans == -1)
return -1;
// Return the ans
let avg = Math.floor((arr[ans].first
+ arr[ans].second)
/ 2);
if (avg > target)
return ans;
return -1;
}
// Function to find indices of desired pair
// for each element of the array of pairs
function findPair(arr, N)
{
// Declaring an unordered map
// to keep the track of
// indices since the order
// is going to be changed
let lookUp = new Array(1000001).fill(0);
// Iterating over the given vector
for (let i = 0; i < N; i++) {
lookUp[arr[i].first] = i;
}
// Sorting the given vector of pairs
// by passing a custom comparator
arr.sort(function (a, b) {
let val1 = Math.floor((a.first + a.second) / 2);
let val2 = Math.floor((b.first + b.second) / 2);
return val1 - val2;
})
// Declaring ans vector to store
// the final answer
let ans = new Array(N)
for (let i = 0; i < N; i++) {
// Average value
let target = Math.floor((arr[i].first
+ arr[i].second)
/ 2);
// Calling lbound() function
let ind = lbound(arr, target);
// If no such pair exists
if (ind == -1)
ans[lookUp[arr[i].first]] = -1;
// If such a pair exists
else
ans[lookUp[arr[i].first]]
= lookUp[arr[ind].first];
}
// Print the final array
for (let x of ans)
document.write(x + ' ')
}
// Driver code
// Initializing a vector of pairs
let arr
= [{ first: 2, second: 3 }, { first: 1, second: 3 }, { first: 3, second: 4 }];
// Size of the vector
let N = arr.length;
findPair(arr, N);
// This code is contributed by Potta Lokesh
</script>
Producción
2 2 -1
Producción
2 2 -1
Complejidad de tiempo: O(N * log(N) )
Espacio auxiliar: O(N)