Dada una array arr[] de tamaño N , la tarea es reorganizar los elementos de la array de modo que el recuento de mínimos locales en la array sea el máximo.
Nota: Se dice que un elemento arr[x] es un mínimo local si es menor o igual que sus dos elementos adyacentes. El primer y el último elemento de la array no pueden considerarse mínimos locales.
Ejemplos:
Entrada: arr[]= {1, 2, 3, 4, 5}
Salida: 3 1 4 2 5
Explicación:
Reorganización de los elementos de la array en {3, 1, 4, 2, 5}. La cuenta de mínimos locales en la array es 2, es decir, {arr[1], arr[3]}, que es la cuenta máxima posible de mínimos locales que se pueden obtener de la array. Por lo tanto, la salida requerida es 3 1 4 2 5.Entrada: arr[]= {1, 2, 3, 4, 5, 6}
Salida: 4 1 5 2 6 3
Enfoque: La idea es utilizar algoritmos de clasificación y la técnica de dos punteros para resolver este problema. Siga los pasos a continuación para resolver este problema:
- Ordene la array en orden ascendente .
- Inicialice dos variables, digamos left = 0 y right = N / 2 para almacenar el índice de los punteros izquierdo y derecho respectivamente.
- Recorra la array y en cada recorrido, primero imprima el valor de arr[right] y luego imprima el valor de arr[left] e incremente el valor de left y right en 1 .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to rearrange array elements to
// maximize count of local minima in the array
void rearrangeArrMaxcntMinima(int arr[], int N)
{
// Sort the array in
// ascending order
sort(arr, arr + N);
// Stores index of
// left pointer
int left = 0;
// Stores index of
// right pointer
int right = N / 2;
// Traverse the array elements
while (left < N / 2 || right < N) {
// if right is less than N
if (right < N) {
// Print array element
cout << arr[right] << " ";
// Update right
right++;
}
if (left < N / 2) {
// Print array element
cout << arr[left] << " ";
// Update left
left++;
}
}
}
// Driver Code
int main()
{
int arr[] = { 1, 2, 3, 4, 5 };
int N = sizeof(arr) / sizeof(arr[0]);
rearrangeArrMaxcntMinima(arr, N);
return 0;
}
Java
// Java program to implement
// the above approach
import java.util.*;
class GFG{
// Function to rearrange array elements to
// maximize count of local minima in the array
static void rearrangeArrMaxcntMinima(int arr[],
int N)
{
// Sort the array in
// ascending order
Arrays.sort(arr);
// Stores index of
// left pointer
int left = 0;
// Stores index of
// right pointer
int right = N / 2;
// Traverse the array elements
while (left < N / 2 || right < N)
{
// If right is less than N
if (right < N)
{
// Print array element
System.out.print(arr[right] + " ");
// Update right
right++;
}
if (left < N / 2)
{
// Print array element
System.out.print(arr[left] + " ");
// Update left
left++;
}
}
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 1, 2, 3, 4, 5 };
int N = arr.length;
rearrangeArrMaxcntMinima(arr, N);
}
}
// This code is contributed by code_hunt
Python3
# Python3 program to implement # the above approach # Function to rearrange array # elements to maximize count of # local minima in the array def rearrangeArrMaxcntMinima(arr, N): # Sort the array in # ascending order arr.sort() # Stores index of # left pointer left = 0 # Stores index of # right pointer right = N // 2 # Traverse the array elements while (left < N // 2 or right < N): # if right is less # than N if (right < N): # Print array element print(arr[right], end = " ") # Update right right += 1 if (left < N // 2): # Print array element print(arr[left], end = " ") # Update left left += 1 # Driver Code if __name__ == "__main__": arr = [1, 2, 3, 4, 5] N = len(arr) rearrangeArrMaxcntMinima(arr, N) # This code is contributed by Chitranayal
C#
// C# program to implement
// the above approach
using System;
class GFG{
// Function to rearrange array elements to
// maximize count of local minima in the array
static void rearrangeArrMaxcntMinima(int []arr,
int N)
{
// Sort the array in
// ascending order
Array.Sort(arr);
// Stores index of
// left pointer
int left = 0;
// Stores index of
// right pointer
int right = N / 2;
// Traverse the array elements
while (left < N / 2 || right < N)
{
// If right is less than N
if (right < N)
{
// Print array element
Console.Write(arr[right] + " ");
// Update right
right++;
}
if (left < N / 2)
{
// Print array element
Console.Write(arr[left] + " ");
// Update left
left++;
}
}
}
// Driver Code
public static void Main(String[] args)
{
int []arr = { 1, 2, 3, 4, 5 };
int N = arr.Length;
rearrangeArrMaxcntMinima(arr, N);
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// Javascript program to implement
// the above approach
// Function to rearrange array elements to
// maximize count of local minima in the array
function rearrangeArrMaxcntMinima(arr, N)
{
// Sort the array in
// ascending order
arr.sort(function(a, b){return a - b;});
// Stores index of
// left pointer
let left = 0;
// Stores index of
// right pointer
let right = Math.floor(N / 2);
// Traverse the array elements
while (left < Math.floor(N / 2) || right < N)
{
// If right is less than N
if (right < N)
{
// Print array element
document.write(arr[right] + " ");
// Update right
right++;
}
if (left < Math.floor(N / 2))
{
// Print array element
document.write(arr[left] + " ");
// Update left
left++;
}
}
}
// Driver Code
let arr = [ 1, 2, 3, 4, 5 ];
let N = arr.length;
rearrangeArrMaxcntMinima(arr, N);
// This code is contributed by avanitrachhadiya2155
</script>
3 1 4 2 5
Complejidad de tiempo: O(N log(N))
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por amartyabhattacharya y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA