Dada una array no ordenada, recorte la array de modo que el doble del mínimo sea mayor que el máximo en la array recortada. Los elementos deben eliminarse de cualquier extremo de la array. El número de retiros debe ser mínimo.
Ejemplos:
Entrada: arr[] = {4, 5, 100, 9, 10, 11, 12, 15, 200}
Salida: 4
Necesitamos eliminar 4 elementos (4, 5, 100, 200)
para que 2*min se convierta en más que máx.Entrada: arr[] = {4, 7, 5, 6}
Salida: 0
No necesitamos eliminar ningún elemento ya que
4*2 > 7Entrada: arr[] = {20, 7, 5, 6}
Salida: 1
Enfoque: Hemos discutido varios enfoques para resolver este problema en tiempo O(n 3 ), O(n 2 * logn) y O(n 2 ) en el artículo anterior . En este artículo, vamos a discutir una solución de tiempo O(n * logn) utilizando los conceptos de ventana deslizante y árbol de segmentos .
- Construya un árbol de segmentos para RangeMinimumQuery y RangeMaximumQuery para la array de entrada dada.
- Tome dos punteros start y end , e inicialice ambos en 0 .
- Si bien end es menor que la longitud de la array de entrada, haga lo siguiente:
- Encuentre min y max en la ventana actual usando Segment Trees construidos en el paso 1.
- Verifique si 2 * min ≤ max , si es así, incremente el puntero de inicio ; de lo contrario, actualice la longitud máxima válida hasta el momento, si es necesario
- Fin del incremento
- length(arr[]) – maxValidLength es la respuesta requerida.
A continuación se muestra la implementación del enfoque anterior:
Java
// Java implementation of the approach
public class GFG {
// Function to return the minimum removals
// required so that the array satisfy
// the given condition
public int removeMinElements(int[] a)
{
int n = a.length;
RangeMinimumQuery rMimQ = new RangeMinimumQuery();
int[] minTree = rMimQ.createSegmentTree(a);
RangeMaximumQuery rMaxQ = new RangeMaximumQuery();
int[] maxTree = rMaxQ.createSegmentTree(a);
int start = 0, end = 0;
// To store min and max in the current window
int min, max;
int maxValidLen = 0;
while (end < n) {
min = rMimQ.rangeMinimumQuery(minTree,
start, end, n);
max = rMaxQ.rangeMaximumQuery(maxTree,
start, end, n);
if (2 * min <= max)
start++;
else
maxValidLen = Math.max(maxValidLen,
end - start + 1);
end++;
}
return n - maxValidLen;
}
class RangeMinimumQuery {
// Creates a new segment tree from
// the given input array
public int[] createSegmentTree(int[] input)
{
int n = input.length;
int segTreeSize = 2 * getNextPowerOfTwo(n) - 1;
int[] segmentTree = new int[segTreeSize];
createSegmentTreeUtil(segmentTree, input,
0, n - 1, 0);
return segmentTree;
}
private void createSegmentTreeUtil(int[] segmentTree,
int[] input, int low,
int high, int pos)
{
if (low == high) {
// Its a leaf node
segmentTree[pos] = input[low];
return;
}
// Construct left and right subtrees and then
// update value for current node
int mid = (low + high) / 2;
createSegmentTreeUtil(segmentTree, input, low,
mid, (2 * pos + 1));
createSegmentTreeUtil(segmentTree, input,
mid + 1, high, (2 * pos + 2));
segmentTree[pos] = Math.min(segmentTree[2 * pos + 1],
segmentTree[2 * pos + 2]);
}
public int rangeMinimumQuery(int[] segmentTree, int from,
int to, int inputSize)
{
return rangeMinimumQueryUtil(segmentTree, 0,
inputSize - 1, from, to, 0);
}
private int rangeMinimumQueryUtil(int[] segmentTree, int low,
int high, int from, int to, int pos)
{
// Total overlap
if (from <= low && to >= high) {
return segmentTree[pos];
}
// No overlap
if (from > high || to < low) {
return Integer.MAX_VALUE;
}
// Partial overlap
int mid = (low + high) / 2;
int left = rangeMinimumQueryUtil(segmentTree, low,
mid, from, to,
(2 * pos + 1));
int right = rangeMinimumQueryUtil(segmentTree,
mid + 1, high, from,
to, (2 * pos + 2));
return Math.min(left, right);
}
}
class RangeMaximumQuery {
// Creates a new segment tree from given input array
public int[] createSegmentTree(int[] input)
{
int n = input.length;
int segTreeSize = 2 * getNextPowerOfTwo(n) - 1;
int[] segmentTree = new int[segTreeSize];
createSegmentTreeUtil(segmentTree, input, 0, n - 1, 0);
return segmentTree;
}
private void createSegmentTreeUtil(int[] segmentTree, int[] input,
int low, int high, int pos)
{
if (low == high) {
// Its a leaf node
segmentTree[pos] = input[low];
return;
}
// Construct left and right subtrees and then
// update value for current node
int mid = (low + high) / 2;
createSegmentTreeUtil(segmentTree, input, low,
mid, (2 * pos + 1));
createSegmentTreeUtil(segmentTree, input,
mid + 1, high, (2 * pos + 2));
segmentTree[pos] = Math.max(segmentTree[2 * pos + 1],
segmentTree[2 * pos + 2]);
}
public int rangeMaximumQuery(int[] segmentTree,
int from, int to, int inputSize)
{
return rangeMaximumQueryUtil(segmentTree, 0,
inputSize - 1, from, to, 0);
}
private int rangeMaximumQueryUtil(int[] segmentTree, int low,
int high, int from, int to, int pos)
{
// Total overlap
if (from <= low && to >= high) {
return segmentTree[pos];
}
// No overlap
if (from > high || to < low) {
return Integer.MIN_VALUE;
}
// Partial overlap
int mid = (low + high) / 2;
int left = rangeMaximumQueryUtil(segmentTree, low,
mid, from, to,
(2 * pos + 1));
int right = rangeMaximumQueryUtil(segmentTree,
mid + 1, high, from,
to, (2 * pos + 2));
return Math.max(left, right);
}
}
// Function to return the minimum power of 2
// which is greater than n
private int getNextPowerOfTwo(int n)
{
int logPart = (int)Math.ceil(Math.log(n)
/ Math.log(2));
return (int)Math.pow(2, logPart);
}
// Driver code
public static void main(String[] args)
{
int[] a = { 4, 5, 100, 9, 10, 11, 12, 15, 200 };
GFG gfg = new GFG();
System.out.println(gfg.removeMinElements(a));
}
}
C#
// C# implementation of the approach
using System;
class GFG
{
// Function to return the minimum removals
// required so that the array satisfy
// the given condition
static int removeMinElements(int[] a)
{
int n = a.Length;
RangeMinimumQuery rMimQ = new RangeMinimumQuery();
int[] minTree = rMimQ.createSegmentTree(a);
RangeMaximumQuery rMaxQ = new RangeMaximumQuery();
int[] maxTree = rMaxQ.createSegmentTree(a);
int start = 0, end = 0;
// To store min and max in the current window
int min, max;
int maxValidLen = 0;
while (end < n)
{
min = rMimQ.rangeMinimumQuery(minTree,
start, end, n);
max = rMaxQ.rangeMaximumQuery(maxTree,
start, end, n);
if (2 * min <= max)
start++;
else
maxValidLen = Math.Max(maxValidLen,
end - start + 1);
end++;
}
return n - maxValidLen;
}
class RangeMinimumQuery {
// Creates a new segment tree from
// the given input array
public int[] createSegmentTree(int[] input)
{
int n = input.Length;
int segTreeSize = 2 * getNextPowerOfTwo(n) - 1;
int[] segmentTree = new int[segTreeSize];
createSegmentTreeUtil(segmentTree, input,
0, n - 1, 0);
return segmentTree;
}
public void createSegmentTreeUtil(int[] segmentTree,
int[] input, int low,
int high, int pos)
{
if (low == high) {
// Its a leaf node
segmentTree[pos] = input[low];
return;
}
// Construct left and right subtrees and then
// update value for current node
int mid = (low + high) / 2;
createSegmentTreeUtil(segmentTree, input, low,
mid, (2 * pos + 1));
createSegmentTreeUtil(segmentTree, input,
mid + 1, high, (2 * pos + 2));
segmentTree[pos] = Math.Min(segmentTree[2 * pos + 1],
segmentTree[2 * pos + 2]);
}
public int rangeMinimumQuery(int[] segmentTree, int from,
int to, int inputSize)
{
return rangeMinimumQueryUtil(segmentTree, 0,
inputSize - 1, from, to, 0);
}
static int rangeMinimumQueryUtil(int[] segmentTree, int low,
int high, int from, int to, int pos)
{
// Total overlap
if (from <= low && to >= high) {
return segmentTree[pos];
}
// No overlap
if (from > high || to < low) {
return int.MaxValue;
}
// Partial overlap
int mid = (low + high) / 2;
int left = rangeMinimumQueryUtil(segmentTree, low,
mid, from, to,
(2 * pos + 1));
int right = rangeMinimumQueryUtil(segmentTree,
mid + 1, high, from,
to, (2 * pos + 2));
return Math.Min(left, right);
}
}
class RangeMaximumQuery {
// Creates a new segment tree from given input array
public int[] createSegmentTree(int[] input)
{
int n = input.Length;
int segTreeSize = 2 * getNextPowerOfTwo(n) - 1;
int[] segmentTree = new int[segTreeSize];
createSegmentTreeUtil(segmentTree, input, 0, n - 1, 0);
return segmentTree;
}
public void createSegmentTreeUtil(int[] segmentTree, int[] input,
int low, int high, int pos)
{
if (low == high) {
// Its a leaf node
segmentTree[pos] = input[low];
return;
}
// Construct left and right subtrees and then
// update value for current node
int mid = (low + high) / 2;
createSegmentTreeUtil(segmentTree, input, low,
mid, (2 * pos + 1));
createSegmentTreeUtil(segmentTree, input,
mid + 1, high, (2 * pos + 2));
segmentTree[pos] = Math.Max(segmentTree[2 * pos + 1],
segmentTree[2 * pos + 2]);
}
public int rangeMaximumQuery(int[] segmentTree,
int from, int to, int inputSize)
{
return rangeMaximumQueryUtil(segmentTree, 0,
inputSize - 1, from, to, 0);
}
public int rangeMaximumQueryUtil(int[] segmentTree, int low,
int high, int from, int to, int pos)
{
// Total overlap
if (from <= low && to >= high) {
return segmentTree[pos];
}
// No overlap
if (from > high || to < low) {
return int.MinValue;
}
// Partial overlap
int mid = (low + high) / 2;
int left = rangeMaximumQueryUtil(segmentTree, low,
mid, from, to,
(2 * pos + 1));
int right = rangeMaximumQueryUtil(segmentTree,
mid + 1, high, from,
to, (2 * pos + 2));
return Math.Max(left, right);
}
}
// Function to return the minimum power of 2
// which is greater than n
static int getNextPowerOfTwo(int n)
{
int logPart = (int)Math.Ceiling(Math.Log(n)
/ Math.Log(2));
return (int)Math.Pow(2, logPart);
}
// Driver code
public static void Main(String[] args)
{
int[] a = { 4, 5, 100, 9, 10, 11, 12, 15, 200 };
Console.WriteLine(removeMinElements(a));
}
}
// This code is contributed by Rajput-Ji
Producción:
4
Publicación traducida automáticamente
Artículo escrito por Narendra_Jha y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA