Dada una array A[] que consta de N enteros, la tarea es encontrar la diferencia mínima entre el elemento más grande y el más pequeño en la array dada después de reemplazar K elementos.
Ejemplos:
Entrada: A[] = {-1, 3, -1, 8, 5, 4}, K = 3
Salida: 2
Explicación: Reemplace A[0] y A[2] por 3 y 4 respectivamente. Reemplace A[3] por 5. La array modificada A[] es {3, 3, 4, 5, 5, 4}. Por lo tanto, salida requerida = (5-3) = 2.Entrada: A[] = {10, 10, 3, 4, 10}, K = 2
Salida: 0
Método de clasificación: la idea es ordenar la array dada . Verifique todas las posibilidades K + 1 de eliminar elementos X ( 0 ≤ X ≤ K ) desde el inicio de la array y eliminar elementos K – X del final de la array y calcule la diferencia mínima posible. Finalmente, imprima la diferencia mínima obtenida.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find minimum difference
// between largest and smallest element
// after K replacements
int minDiff(int A[], int K, int n)
{
// Sort array in ascending order
sort(A, A + n);
if (n <= K)
return 0;
// Minimum difference
int mindiff = A[n - 1] - A[0];
if (K == 0)
return mindiff;
// Check for all K + 1 possibilities
for(int i = 0, j = n - 1 - K; j < n;)
{
mindiff = min(
mindiff, A[j] - A[i]);
i++;
j++;
}
// Return answer
return mindiff;
}
// Driver Code
int main()
{
// Given array
int A[] = { -1, 3, -1, 8, 5, 4 };
int K = 3;
// Length of array
int n = sizeof(A) / sizeof(A[0]);
// Prints the minimum possible difference
cout << minDiff(A, K, n);
return 0;
}
// This code is contributed by 29AjayKumar
Java
// Java program for the above approach
import java.util.*;
class GFG {
// Function to find minimum difference
// between largest and smallest element
// after K replacements
static int minDiff(int[] A, int K)
{
// Sort array in ascending order
Arrays.sort(A);
// Length of array
int n = A.length;
if (n <= K)
return 0;
// Minimum difference
int mindiff = A[n - 1] - A[0];
if (K == 0)
return mindiff;
// Check for all K + 1 possibilities
for (int i = 0, j = n - 1 - K; j < n;) {
mindiff = Math.min(
mindiff, A[j] - A[i]);
i++;
j++;
}
// Return answer
return mindiff;
}
// Driver Code
public static void main(String[] args)
{
// Given array
int A[] = { -1, 3, -1, 8, 5, 4 };
int K = 3;
// Prints the minimum possible difference
System.out.println(minDiff(A, K));
}
}
Python3
# Python3 program for the above approach # Function to find minimum difference # between largest and smallest element # after K replacements def minDiff(A, K): # Sort array in ascending order A.sort(); # Length of array n = len(A); if (n <= K): return 0; # Minimum difference mindiff = A[n - 1] - A[0]; if (K == 0): return mindiff; # Check for all K + 1 possibilities i = 0; for j in range(n - 1 - K, n): mindiff = min(mindiff, A[j] - A[i]); i += 1; j += 1; # Return answer return mindiff; # Driver Code if __name__ == '__main__': # Given array A = [-1, 3, -1, 8, 5, 4]; K = 3; # Prints the minimum possible difference print(minDiff(A, K)); # This code is contributed by 29AjayKumar
C#
// C# program for the above approach
using System;
class GFG{
// Function to find minimum difference
// between largest and smallest element
// after K replacements
static int minDiff(int[] A, int K)
{
// Sort array in ascending order
Array.Sort(A);
// Length of array
int n = A.Length;
if (n <= K)
return 0;
// Minimum difference
int mindiff = A[n - 1] - A[0];
if (K == 0)
return mindiff;
// Check for all K + 1 possibilities
for(int i = 0, j = n - 1 - K; j < n;)
{
mindiff = Math.Min(
mindiff, A[j] - A[i]);
i++;
j++;
}
// Return answer
return mindiff;
}
// Driver Code
public static void Main(String[] args)
{
// Given array
int []A = { -1, 3, -1, 8, 5, 4 };
int K = 3;
// Prints the minimum possible difference
Console.WriteLine(minDiff(A, K));
}
}
// This code is contributed by shikhasingrajput
Javascript
<script>
// Javascript program for the above approach
// Function to find minimum difference
// between largest and smallest element
// after K replacements
function minDiff(A, K)
{
// Sort array in ascending order
A.sort(function(a, b){return a - b});
// Length of array
let n = A.length;
if (n <= K)
return 0;
// Minimum difference
let mindiff = A[n - 1] - A[0];
if (K == 0)
return mindiff;
// Check for all K + 1 possibilities
for(let i = 0, j = n - 1 - K; j < n;)
{
mindiff = Math.min(mindiff, A[j] - A[i]);
i++;
j++;
}
// Return answer
return mindiff;
}
// Given array
let A = [ -1, 3, -1, 8, 5, 4 ];
let K = 3;
// Prints the minimum possible difference
document.write(minDiff(A, K));
// This code is contributed by mukesh07.
</script>
Producción:
2
Complejidad temporal: O(NlogN)
Espacio auxiliar: O(1)
Enfoque basado en almacenamiento dinámico: este enfoque es similar al enfoque anterior. Encuentre loselementos de array K mínimo y K máximo usando Min Heap y Max Heap respectivamente.
Siga los pasos a continuación para resolver el problema:
- Inicialice dos PriorityQueues , min-heap y max-heap .
- Recorra la array dada y agregue todos los elementos uno por uno en Heaps . Si el tamaño del Montón excede K , en cualquiera de los montones, elimine el elemento presente en la parte superior de esa Cola .
- Almacene los elementos K máximo y mínimo en dos arrays separadas, maxList y minList , e inicialice una variable, digamos minDiff para almacenar la diferencia mínima.
- Itere sobre las arrays y para cada índice, digamos i , actualice minDiff como minDiff = min(minDiff, maxList[i]-minList[ K – i ]) e imprima el valor final de minDiff como la respuesta requerida.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find minimum difference
// between the largest and smallest
// element after K replacements
int minDiff(int A[], int K, int N)
{
if (N <= K + 1)
return 0;
// Create a MaxHeap
priority_queue<int, vector<int>, greater<int>>
maxHeap;
// Create a MinHeap
priority_queue<int> minHeap;
// Update maxHeap and MinHeap with highest
// and smallest K elements respectively
for (int i = 0; i < N; i++)
{
// Insert current element
// into the MaxHeap
maxHeap.push(A[i]);
// If maxHeap size exceeds K + 1
if (maxHeap.size() > K + 1)
// Remove top element
maxHeap.pop();
// Insert current element
// into the MaxHeap
minHeap.push(A[i]);
// If maxHeap size exceeds K + 1
if (minHeap.size() > K + 1)
// Remove top element
minHeap.pop();
}
// Store all max element from maxHeap
vector<int> maxList;
while (maxHeap.size() > 0)
{
maxList.push_back(maxHeap.top());
maxHeap.pop();
}
// Store all min element from minHeap
vector<int> minList;
while (minHeap.size() > 0)
{
minList.push_back(minHeap.top());
minHeap.pop();
}
int mindiff = INT_MAX;
// Generating all K + 1 possibilities
for (int i = 0; i <= K; i++)
{
mindiff = min(mindiff, maxList[i] - minList[K - i]);
}
// Return answer
return mindiff;
}
// Driver Code
int main()
{
// Given array
int A[] = { -1, 3, -1, 8, 5, 4 };
int N = sizeof(A) / sizeof(A[0]);
int K = 3;
// Function call
cout << minDiff(A, K, N);
return 0;
}
// This code is contributed by Dharanendra L V
Java
// Java program for above approach
import java.util.*;
import java.lang.*;
class GFG {
// Function to find minimum difference
// between the largest and smallest
// element after K replacements
static int minDiff(int[] A, int K)
{
if (A.length <= K + 1)
return 0;
// Create a MaxHeap
PriorityQueue<Integer> maxHeap
= new PriorityQueue<>();
// Create a MinHeap
PriorityQueue<Integer> minHeap
= new PriorityQueue<>(
Collections.reverseOrder());
// Update maxHeap and MinHeap with highest
// and smallest K elements respectively
for (int n : A) {
// Insert current element
// into the MaxHeap
maxHeap.add(n);
// If maxHeap size exceeds K + 1
if (maxHeap.size() > K + 1)
// Remove top element
maxHeap.poll();
// Insert current element
// into the MaxHeap
minHeap.add(n);
// If maxHeap size exceeds K + 1
if (minHeap.size() > K + 1)
// Remove top element
minHeap.poll();
}
// Store all max element from maxHeap
List<Integer> maxList = new ArrayList<>();
while (maxHeap.size() > 0)
maxList.add(maxHeap.poll());
// Store all min element from minHeap
List<Integer> minList = new ArrayList<>();
while (minHeap.size() > 0)
minList.add(minHeap.poll());
int mindiff = Integer.MAX_VALUE;
// Generating all K + 1 possibilities
for (int i = 0; i <= K; i++) {
mindiff = Math.min(mindiff,
maxList.get(i)
- minList.get(K - i));
}
// Return answer
return mindiff;
}
// Driver Code
public static void main(String[] args)
{
// Given array
int A[] = { -1, 3, -1, 8, 5, 4 };
int K = 3;
// Function call
System.out.println(minDiff(A, K));
}
}
Python3
# Python3 program for above approach import sys # Function to find minimum difference # between the largest and smallest # element after K replacements def minDiff(A, K) : if (len(A) <= K + 1) : return 0 # Create a MaxHeap maxHeap = [] # Create a MinHeap minHeap = [] # Update maxHeap and MinHeap with highest # and smallest K elements respectively for n in A : # Insert current element # into the MaxHeap maxHeap.append(n) maxHeap.sort() # If maxHeap size exceeds K + 1 if (len(maxHeap) > K + 1) : # Remove top element del maxHeap[0] # Insert current element # into the MaxHeap minHeap.append(n) minHeap.sort() minHeap.reverse() # If maxHeap size exceeds K + 1 if (len(minHeap) > K + 1) : # Remove top element del minHeap[0] # Store all max element from maxHeap maxList = [] while (len(maxHeap) > 0) : maxList.append(maxHeap[0]) del maxHeap[0] # Store all min element from minHeap minList = [] while (len(minHeap) > 0) : minList.append(minHeap[0]) del minHeap[0] mindiff = sys.maxsize # Generating all K + 1 possibilities for i in range(K) : mindiff = min(mindiff, maxList[i] - minList[K - i]) # Return answer return mindiff # Given array A = [ -1, 3, -1, 8, 5, 4 ] K = 3 # Function call print(minDiff(A, K)) # This code is contributed by divyesh072019.
C#
// C# program for above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to find minimum difference
// between the largest and smallest
// element after K replacements
static int minDiff(int[] A, int K)
{
if (A.Length <= K + 1)
return 0;
// Create a MaxHeap
List<int> maxHeap = new List<int>();
// Create a MinHeap
List<int> minHeap = new List<int>();
// Update maxHeap and MinHeap with highest
// and smallest K elements respectively
foreach(int n in A)
{
// Insert current element
// into the MaxHeap
maxHeap.Add(n);
maxHeap.Sort();
// If maxHeap size exceeds K + 1
if (maxHeap.Count > K + 1)
// Remove top element
maxHeap.RemoveAt(0);
// Insert current element
// into the MaxHeap
minHeap.Add(n);
minHeap.Sort();
minHeap.Reverse();
// If maxHeap size exceeds K + 1
if (minHeap.Count > K + 1)
// Remove top element
minHeap.RemoveAt(0);
}
// Store all max element from maxHeap
List<int> maxList = new List<int>();
while (maxHeap.Count > 0)
{
maxList.Add(maxHeap[0]);
maxHeap.RemoveAt(0);
}
// Store all min element from minHeap
List<int> minList = new List<int>();
while (minHeap.Count > 0)
{
minList.Add(minHeap[0]);
minHeap.RemoveAt(0);
}
int mindiff = Int32.MaxValue;
// Generating all K + 1 possibilities
for(int i = 0; i < K; i++)
{
mindiff = Math.Min(mindiff,
maxList[i] -
minList[K - i]);
}
// Return answer
return mindiff;
}
// Driver code
static void Main()
{
// Given array
int[] A = { -1, 3, -1, 8, 5, 4 };
int K = 3;
// Function call
Console.WriteLine(minDiff(A, K));
}
}
// This code is contributed by divyeshrabadiya07
Javascript
<script>
// Javascript program for above approach
// Function to find minimum difference
// between the largest and smallest
// element after K replacements
function minDiff(A, K, N)
{
if (N <= K + 1)
return 0;
// Create a MaxHeap
var maxHeap = [];
// Create a MinHeap
var minHeap = [];
// Update maxHeap and MinHeap with highest
// and smallest K elements respectively
for (var i = 0; i < N; i++)
{
// Insert current element
// into the MaxHeap
maxHeap.push(A[i]);
maxHeap.sort((a,b)=>b-a);
// If maxHeap size exceeds K + 1
if (maxHeap.length > K + 1)
// Remove top element
maxHeap.pop();
// Insert current element
// into the MaxHeap
minHeap.push(A[i]);
minHeap.sort((a,b)=>a-b);
// If maxHeap size exceeds K + 1
if (minHeap.length > K + 1)
// Remove top element
minHeap.pop();
}
// Store all max element from maxHeap
var maxList = [];
while (maxHeap.length > 0)
{
maxList.push(maxHeap[maxHeap.length-1]);
maxHeap.pop();
}
// Store all min element from minHeap
var minList = [];
while (minHeap.length > 0)
{
minList.push(minHeap[minHeap.length-1]);
minHeap.pop();
}
var mindiff = 1000000000;
// Generating all K + 1 possibilities
for (var i = 0; i <= K; i++)
{
mindiff = Math.min(mindiff, maxList[i] - minList[K - i]);
}
// Return answer
return mindiff;
}
// Driver Code
// Given array
var A = [-1, 3, -1, 8, 5, 4];
var N = A.length;
var K = 3;
// Function call
document.write(minDiff(A, K, N));
// This code is contributed by noob2000.
</script>
Producción:
2
Complejidad de tiempo: O(NlogN) donde N es el tamaño de la array dada.
Espacio Auxiliar: O(N)