Dada una array arr[] de N enteros, la tarea es maximizar el número de índices de modo que un elemento sea mayor que el elemento a su izquierda, es decir, arr[i+1] > arr[i] después de reorganizar la array.
Ejemplos:
Entrada: arr[] = {200, 100, 100, 200}
Salida: 2
Explicación:
Al ordenar la array de la siguiente manera tenemos: arr[] = {100, 200, 100, 200}
Los índices posibles son 0 y 2 tal que:
arr[1] > arr[0] (200 > 100)
arr[3] > arr[2] (200 > 100)
Entrada: arr[] = {1, 8, 5, 9, 8, 8, 7, 7, 5, 7, 7}
Salida: 7
Explicación:
Al organizar la array de la siguiente manera tenemos: arr[] = {1, 5, 7, 8, 9, 5, 7, 8, 7, 8, 4}
Los índices posibles son 0, 1, 2, 3, 5, 6 y 7 tales que:
arr[1] > arr[0] (5 > 1)
arr[2] > arr[1] (7 > 5)
array[3] > array[2] (8 > 7)
array[4] > array[3] (9 > 8)
array[6] > array[5] (7 > 5)
array[7] > array[6] (8 > 7)
array[8] > array[7] (8 > 7)
Enfoque: este problema se puede resolver utilizando el enfoque codicioso . A continuación se muestran los pasos:
- Para obtener el número máximo de índices (digamos i ) tal que arr[i+1] > arr[i] , organice los elementos de arr[] de modo que el conjunto de todos los elementos únicos ocurra primero, luego ocurra el siguiente conjunto de elementos únicos después del primer juego hasta que todos los elementos estén ordenados.
Por ejemplo:
Sea arr[] = {1, 8, 5, 9, 8, 8, 7, 7, 5, 7, 7}
1er conjunto = {1, 5, 7, 8, 9}
2do conjunto = {5, 7, 8}
3.er conjunto = {7, 8}
4.º conjunto = {4}
Ahora el nuevo arreglo será:
arr[] = {1, 5, 7, 8, 9 , 5 , 7, 8 , 7, 8 , 4 }
- Después del arreglo anterior, el elemento con el valor más alto no formará parte de la condición dada ya que es seguido por un número menor que él mismo.
- Por lo tanto, el número total de pares que satisfacen la condición dada puede estar dado por:
pares_totales = (número_de_elementos – frecuencia_más_alta_de_un_número)
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program of the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the maximum pairs
// such that arr[i+1] > arr[i]
void countPairs(int arr[], int N)
{
// To store the frequency of the
// element in arr[]
unordered_map<int, int> M;
// Store the frequency in map M
for (int i = 0; i < N; i++) {
M[arr[i]]++;
}
int maxFreq = 0;
// To find the maximum frequency
// store in map M
for (auto& it : M) {
maxFreq = max(maxFreq,
it.second);
}
// Print the maximum number of
// possible pairs
cout << N - maxFreq << endl;
}
// Driver Code
int main()
{
int arr[] = { 1, 8, 5, 9, 8, 8, 7,
7, 5, 7, 7 };
int N = sizeof(arr) / sizeof(arr[0]);
countPairs(arr, N);
return 0;
}
Java
// Java program of the above approach
import java.util.*;
class GFG{
// Function to find the maximum pairs
// such that arr[i+1] > arr[i]
static void countPairs(int arr[], int N)
{
// To store the frequency of the
// element in arr[]
HashMap<Integer,Integer> mp = new HashMap<Integer,Integer>();
// Store the frequency in map M
for (int i = 0; i < N; i++) {
if(mp.containsKey(arr[i])){
mp.put(arr[i], mp.get(arr[i])+1);
}else{
mp.put(arr[i], 1);
}
}
int maxFreq = 0;
// To find the maximum frequency
// store in map M
for (Map.Entry<Integer,Integer> it : mp.entrySet()) {
maxFreq = Math.max(maxFreq,
it.getValue());
}
// Print the maximum number of
// possible pairs
System.out.print(N - maxFreq +"\n");
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 1, 8, 5, 9, 8, 8, 7,
7, 5, 7, 7 };
int N = arr.length;
countPairs(arr, N);
}
}
// This code is contributed by Rajput-Ji
Python3
# Python3 implementation of the above approach # Function to find the maximum pairs # such that arr[i + 1] > arr[i] def countPairs(arr, N) : # To store the frequency of the # element in arr[] M = dict.fromkeys(arr, 0); # Store the frequency in map M for i in range(N) : M[arr[i]] += 1; maxFreq = 0; # To find the maximum frequency # store in map M for it in M.values() : maxFreq = max(maxFreq,it); # Print the maximum number of # possible pairs print(N - maxFreq); # Driver Code if __name__ == "__main__" : arr = [ 1, 8, 5, 9, 8, 8, 7, 7, 5, 7, 7 ]; N = len(arr); countPairs(arr, N); # This code is contributed by AnkitRai01
C#
// C# program of the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to find the maximum pairs
// such that arr[i+1] > arr[i]
static void countPairs(int []arr, int N)
{
// To store the frequency of the
// element in []arr
Dictionary<int,int> mp = new Dictionary<int,int>();
// Store the frequency in map M
for (int i = 0; i < N; i++) {
if(mp.ContainsKey(arr[i])){
mp[arr[i]] = mp[arr[i]]+1;
}else{
mp.Add(arr[i], 1);
}
}
int maxFreq = 0;
// To find the maximum frequency
// store in map M
foreach (KeyValuePair<int,int> it in mp) {
maxFreq = Math.Max(maxFreq,
it.Value);
}
// Print the maximum number of
// possible pairs
Console.Write(N - maxFreq +"\n");
}
// Driver Code
public static void Main(String[] args)
{
int []arr = { 1, 8, 5, 9, 8, 8, 7,
7, 5, 7, 7 };
int N = arr.Length;
countPairs(arr, N);
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// Js program of the above approach
// Function to find the maximum pairs
// such that arr[i+1] > arr[i]
function countPairs( arr, N){
// To store the frequency of the
// element in arr[]
let M = new Map();
// Store the frequency in map M
for (let i = 0; i < N; i++) {
if(M[arr[i]])
M[arr[i]]++;
else
M[arr[i]] = 1
}
let maxFreq = 0;
// To find the maximum frequency
// store in map M
for (let it in M) {
maxFreq = Math.max(maxFreq,
M[it]);
}
// Print the maximum number of
// possible pairs
document.write(N - maxFreq,'<br>');
}
// Driver Code
let a = [ 1, 8, 5, 9, 8, 8, 7,
7, 5, 7, 7 ];
let N = a.length;
countPairs(a, N);
</script>
7
Complejidad de tiempo: O(N), donde N es el número de elementos en la array.
Espacio Auxiliar: O(N), donde N es el número de elementos en el arreglo.
Publicación traducida automáticamente
Artículo escrito por AyanChowdhury y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA