Dada la array flotante ordenada arr[] . Comprueba si arr[] se puede reorganizar de modo que su media sea igual a su mediana.
Ejemplos :
Entrada : arr[] = {1.0, 3.0, 6.0, 9.0, 12.0, 32.0}
Salida : Sí
Explicación: La media de la array dada es (1.0 + 3.0 + 6.0 + 9.0 + 12.0 + 32.0) / 6 = 10.5.
Reorganizando la array dada como {1.0, 3.0, 9.0, 12.0, 6.0, 32.0}, aquí la mediana es (9.0 + 12.0) / 2 = 10.5Entrada : arr[] = {8.0, 13.0, 15.0}
Salida : No
Enfoque: el problema dado se puede resolver utilizando el enfoque de búsqueda binaria y dos punteros . Si el tamaño de arr[] es impar, significa que la mediana es un elemento único que se puede buscar mediante la búsqueda binaria. Si el tamaño de la array es par, se puede usar el enfoque de dos punteros porque la mediana estará compuesta por dos elementos. Siga los pasos a continuación para resolver el problema dado.
- Inicialice una variable, digamos, mean para almacenar la media de arr[] .
- Compruebe si el tamaño de arr[] es par o impar.
- si el tamaño de arr[] es par
- Utilice el enfoque de dos punteros para buscar dos elementos cuyo promedio = media .
- Inicialice dos punteros como i=0, j=n-1 .
- Realice el enfoque de dos punteros para buscar la mediana en arr[] .
- si el tamaño de arr[] es impar
- Aplique la búsqueda binaria para encontrar si la media está presente en arr[] o no.
- si el tamaño de arr[] es par
- Si es media se encuentra devuelve Sí , de lo contrario No .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <iostream>
using namespace std;
// Function to return true or false if
// size of array is odd
bool binarySearch(float arr[], int size, float key)
{
int low = 0, high = size - 1, mid;
while (low <= high) {
// To prevent overflow
mid = low + (high - low) / 2;
// If element is greater than mid, then
// it can only be present in right subarray
if (key > arr[mid])
low = mid + 1;
// If element is smaller than mid, then
// it can only be present in left subarray
else if (key < arr[mid])
high = mid - 1;
// Else the element is present at the middle
// then return 1
else
return 1;
}
// when element is not present
// in array then return 0
return 0;
}
// Function to return true or false
// if size of array is even
bool twoPointers(float arr[], int N, float mean)
{
int i = 0, j = N - 1;
while (i < j) {
// Calculating Candidate Median
float temp = (arr[i] + arr[j]) / 2;
// If Candidate Median if greater
// than Mean then decrement j
if (temp > mean)
j--;
// If Candidate Median if less
// than Mean then increment i
else if (temp < mean)
i++;
// If Candidate Median if equal
// to Mean then return 1
else
return 1;
}
// when No candidate found for mean
return 0;
}
// Function to return true if Mean
// can be equal to any candidate
// median otherwise return false
bool checkArray(float arr[], int N)
{
// Calculating Mean
float sum = 0;
for (int i = 0; i < N; i++)
sum += arr[i];
float mean = sum / N;
// If N is Odd
if (N & 1)
return binarySearch(arr, N, mean);
// If N is even
else
return twoPointers(arr, N, mean);
}
// Driver Code
int main()
{
float arr[] = { 1.0, 3.0, 6.0, 9.0, 12.0, 32.0 };
int N = sizeof(arr) / sizeof(arr[0]);
if (checkArray(arr, N))
cout << "Yes";
else
cout << "No";
return 0;
}
Java
// Java program for the above approach
import java.io.*;
public class GFG{
// Function to return true or false if
// size of array is odd
static boolean binarySearch(float []arr, int size, float key)
{
int low = 0, high = size - 1, mid;
while (low <= high) {
// To prevent overflow
mid = low + (high - low) / 2;
// If element is greater than mid, then
// it can only be present in right subarray
if (key > arr[mid])
low = mid + 1;
// If element is smaller than mid, then
// it can only be present in left subarray
else if (key < arr[mid])
high = mid - 1;
// Else the element is present at the middle
// then return 1
else
return true;
}
// when element is not present
// in array then return 0
return false;
}
// Function to return true or false
// if size of array is even
static boolean twoPointers(float []arr, int N, float mean)
{
int i = 0, j = N - 1;
while (i < j) {
// Calculating Candidate Median
float temp = (arr[i] + arr[j]) / 2;
// If Candidate Median if greater
// than Mean then decrement j
if (temp > mean)
j--;
// If Candidate Median if less
// than Mean then increment i
else if (temp < mean)
i++;
// If Candidate Median if equal
// to Mean then return 1
else
return true;
}
// when No candidate found for mean
return false;
}
// Function to return true if Mean
// can be equal to any candidate
// median otherwise return false
static boolean checkArray(float []arr, int N)
{
// Calculating Mean
float sum = 0;
for (int i = 0; i < N; i++)
sum += arr[i];
float mean = sum / N;
// If N is Odd
if ((N & 1)!=0)
return binarySearch(arr, N, mean);
// If N is even
else
return twoPointers(arr, N, mean);
}
// Driver Code
public static void main(String []args)
{
float []arr = { 1.0f, 3.0f, 6.0f, 9.0f, 12.0f, 32.0f };
int N = arr.length;
if (checkArray(arr, N))
System.out.println("Yes");
else
System.out.println("No");
}
}
// This code is contributed by AnkThon.
Python3
# python program for the above approach
# Function to return true or false if
# size of array is odd
def binarySearch(arr, size, key):
low = 0
high = size - 1
while (low <= high):
# To prevent overflow
mid = low + (high - low) // 2
# If element is greater than mid, then
# it can only be present in right subarray
if (key > arr[mid]):
low = mid + 1
# If element is smaller than mid, then
# it can only be present in left subarray
elif (key < arr[mid]):
high = mid - 1
# Else the element is present at the middle
# then return 1
else:
return 1
# when element is not present
# in array then return 0
return 0
# Function to return true or false
# if size of array is even
def twoPointers(arr, N, mean):
i = 0
j = N - 1
while (i < j):
# Calculating Candidate Median
temp = (arr[i] + arr[j]) / 2
# If Candidate Median if greater
# than Mean then decrement j
if (temp > mean):
j = j - 1
# If Candidate Median if less
# than Mean then increment i
elif (temp < mean):
i = i + 1
# If Candidate Median if equal
# to Mean then return 1
else:
return 1
# when No candidate found for mean
return 0
# Function to return true if Mean
# can be equal to any candidate
# median otherwise return false
def checkArray(arr, N):
# Calculating Mean
sum = 0
for i in range(0, N):
sum += arr[i]
mean = sum / N
# If N is Odd
if (N & 1):
return binarySearch(arr, N, mean)
# If N is even
else:
return twoPointers(arr, N, mean)
# Driver Code
if __name__ == "__main__":
arr = [1.0, 3.0, 6.0, 9.0, 12.0, 32.0]
N = len(arr)
if (checkArray(arr, N)):
print("Yes")
else:
print("No")
# This code is contributed by rakeshsahni
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to return true or false if
// size of array is odd
static bool binarySearch(float []arr, int size, float key)
{
int low = 0, high = size - 1, mid;
while (low <= high) {
// To prevent overflow
mid = low + (high - low) / 2;
// If element is greater than mid, then
// it can only be present in right subarray
if (key > arr[mid])
low = mid + 1;
// If element is smaller than mid, then
// it can only be present in left subarray
else if (key < arr[mid])
high = mid - 1;
// Else the element is present at the middle
// then return 1
else
return true;
}
// when element is not present
// in array then return 0
return false;
}
// Function to return true or false
// if size of array is even
static bool twoPointers(float []arr, int N, float mean)
{
int i = 0, j = N - 1;
while (i < j) {
// Calculating Candidate Median
float temp = (arr[i] + arr[j]) / 2;
// If Candidate Median if greater
// than Mean then decrement j
if (temp > mean)
j--;
// If Candidate Median if less
// than Mean then increment i
else if (temp < mean)
i++;
// If Candidate Median if equal
// to Mean then return 1
else
return true;
}
// when No candidate found for mean
return false;
}
// Function to return true if Mean
// can be equal to any candidate
// median otherwise return false
static bool checkArray(float []arr, int N)
{
// Calculating Mean
float sum = 0;
for (int i = 0; i < N; i++)
sum += arr[i];
float mean = sum / N;
// If N is Odd
if ((N & 1)!=0)
return binarySearch(arr, N, mean);
// If N is even
else
return twoPointers(arr, N, mean);
}
// Driver Code
public static void Main()
{
float []arr = { 1.0f, 3.0f, 6.0f, 9.0f, 12.0f, 32.0f };
int N = arr.Length;
if (checkArray(arr, N))
Console.Write("Yes");
else
Console.Write("No");
}
}
// This code is contributed by SURENDRA_GANGWAR.
Javascript
<script>
// JavaScript program for the above approach
// Function to return true or false if
// size of array is odd
const binarySearch = (arr, size, key) => {
let low = 0, high = size - 1, mid;
while (low <= high) {
// To prevent overflow
mid = low + parseInt((high - low) / 2);
// If element is greater than mid, then
// it can only be present in right subarray
if (key > arr[mid])
low = mid + 1;
// If element is smaller than mid, then
// it can only be present in left subarray
else if (key < arr[mid])
high = mid - 1;
// Else the element is present at the middle
// then return 1
else
return 1;
}
// when element is not present
// in array then return 0
return 0;
}
// Function to return true or false
// if size of array is even
const twoPointers = (arr, N, mean) => {
let i = 0, j = N - 1;
while (i < j) {
// Calculating Candidate Median
let temp = (arr[i] + arr[j]) / 2;
// If Candidate Median if greater
// than Mean then decrement j
if (temp > mean)
j--;
// If Candidate Median if less
// than Mean then increment i
else if (temp < mean)
i++;
// If Candidate Median if equal
// to Mean then return 1
else
return 1;
}
// when No candidate found for mean
return 0;
}
// Function to return true if Mean
// can be equal to any candidate
// median otherwise return false
const checkArray = (arr, N) => {
// Calculating Mean
let sum = 0;
for (let i = 0; i < N; i++)
sum += arr[i];
let mean = sum / N;
// If N is Odd
if (N & 1)
return binarySearch(arr, N, mean);
// If N is even
else
return twoPointers(arr, N, mean);
}
// Driver Code
let arr = [1.0, 3.0, 6.0, 9.0, 12.0, 32.0];
let N = arr.length;
if (checkArray(arr, N))
document.write("Yes");
else
document.write("No");
// This code is contributed by rakeshsahni
</script>
Producción
Yes
Complejidad temporal : O(N), cuando N es par.
O(logN), cuando N es impar.
Espacio Auxiliar : O(1).
Publicación traducida automáticamente
Artículo escrito por akashjha2671 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA