Dada una array de enteros y dos números k1 y k2. Encuentre la suma de todos los elementos entre los dos k1’th y k2’th elementos más pequeños de la array. Se puede suponer que (1 <= k1 < k2 <= n) y todos los elementos de la array son distintos.
Ejemplos:
Input : arr[] = {20, 8, 22, 4, 12, 10, 14}, k1 = 3, k2 = 6
Output : 26
3rd smallest element is 10. 6th smallest element
is 20. Sum of all element between k1 & k2 is
12 + 14 = 26
Input : arr[] = {10, 2, 50, 12, 48, 13}, k1 = 2, k2 = 6
Output : 73
Método 1 (Clasificación): Primero ordene la array dada usando un algoritmo de clasificación O (n log n) como Merge Sort , Heap Sort , etc. y devuelva la suma de todos los elementos entre el índice k1 y k2 en la array ordenada.
Implementación:
C++
// C++ program to find sum of all element between
// to K1'th and k2'th smallest elements in array
#include <bits/stdc++.h>
using namespace std;
// Returns sum between two kth smallest elements of the array
int sumBetweenTwoKth(int arr[], int n, int k1, int k2)
{
// Sort the given array
sort(arr, arr + n);
/* Below code is equivalent to
int result = 0;
for (int i=k1; i<k2-1; i++)
result += arr[i]; */
return accumulate(arr + k1, arr + k2 - 1, 0);
}
// Driver program
int main()
{
int arr[] = { 20, 8, 22, 4, 12, 10, 14 };
int k1 = 3, k2 = 6;
int n = sizeof(arr) / sizeof(arr[0]);
cout << sumBetweenTwoKth(arr, n, k1, k2);
return 0;
}
Java
// Java program to find sum of all element
// between to K1'th and k2'th smallest
// elements in array
import java.util.Arrays;
class GFG {
// Returns sum between two kth smallest
// element of array
static int sumBetweenTwoKth(int arr[],
int k1, int k2)
{
// Sort the given array
Arrays.sort(arr);
// Below code is equivalent to
int result = 0;
for (int i = k1; i < k2 - 1; i++)
result += arr[i];
return result;
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 20, 8, 22, 4, 12, 10, 14 };
int k1 = 3, k2 = 6;
int n = arr.length;
System.out.print(sumBetweenTwoKth(arr,
k1, k2));
}
}
// This code is contributed by Anant Agarwal.
Python3
# Python program to find sum of # all element between to K1'th and # k2'th smallest elements in array # Returns sum between two kth # smallest element of array def sumBetweenTwoKth(arr, n, k1, k2): # Sort the given array arr.sort() result = 0 for i in range(k1, k2-1): result += arr[i] return result # Driver code arr = [ 20, 8, 22, 4, 12, 10, 14 ] k1 = 3; k2 = 6 n = len(arr) print(sumBetweenTwoKth(arr, n, k1, k2)) # This code is contributed by Anant Agarwal.
C#
// C# program to find sum of all element
// between to K1'th and k2'th smallest
// elements in array
using System;
class GFG {
// Returns sum between two kth smallest
// element of array
static int sumBetweenTwoKth(int[] arr, int n,
int k1, int k2)
{
// Sort the given array
Array.Sort(arr);
// Below code is equivalent to
int result = 0;
for (int i = k1; i < k2 - 1; i++)
result += arr[i];
return result;
}
// Driver code
public static void Main()
{
int[] arr = { 20, 8, 22, 4, 12, 10, 14 };
int k1 = 3, k2 = 6;
int n = arr.Length;
Console.Write(sumBetweenTwoKth(arr, n, k1, k2));
}
}
// This code is contributed by nitin mittal.
PHP
<?php
// PHP program to find sum of all element between
// to K1'th and k2'th smallest elements in array
// Returns sum between two kth smallest elements of the array
function sumBetweenTwoKth($arr, $n, $k1, $k2)
{
// Sort the given array
sort($arr);
// Below code is equivalent to
$result = 0;
for ($i = $k1; $i < $k2 - 1; $i++)
$result += $arr[$i];
return $result;
}
// Driver program
$arr = array( 20, 8, 22, 4, 12, 10, 14 );
$k1 = 3;
$k2 = 6;
$n = count($arr);;
echo sumBetweenTwoKth($arr, $n, $k1, $k2);
// This code is contributed by mits
?>
Javascript
<script>
// Javascript program to find sum of all element
// between to K1'th and k2'th smallest
// elements in array
// Returns sum between two kth smallest
// element of array
function sumBetweenTwoKth(arr, k1 , k2)
{
// Sort the given array
arr.sort(function(a, b){return a - b});
// Below code is equivalent to
var result = 0;
for(var i = k1; i < k2 - 1; i++)
result += arr[i];
return result;
}
// Driver code
var arr = [ 20, 8, 22, 4, 12, 10, 14 ];
var k1 = 3, k2 = 6;
var n = arr.length;
document.write(sumBetweenTwoKth(arr,
k1, k2));
// This code is contributed by shikhasingrajput
</script>
Producción
26
Complejidad de tiempo : O (n log n)
Método 2 (usando Min Heap):
Podemos optimizar la solución anterior utilizando un montón mínimo.
- Cree un montón mínimo de todos los elementos de la array. (Este paso toma tiempo O(n))
- Extraiga el tiempo mínimo k1 (este paso requiere tiempo O (K1 Log n))
- Extraiga el mínimo k2 – k1 – 1 vez y sume todos los elementos extraídos. (Este paso toma O ((K2 – k1) * Log n) tiempo)
Análisis de Complejidad de Tiempo:
- Al hacer un análisis simple, podemos observar que la complejidad de tiempo del paso 3 [Determinación del paso para la complejidad de tiempo general] también puede llegar a O (nlogn).
- Echa un vistazo a la siguiente descripción:
- La complejidad temporal del paso 3 es: O((k2-k1)*log(n)) .
- En el peor de los casos, (k2-k1) sería casi O(n) [Asumir la situación cuando k1=0 y k2=len(arr)-1]
- Cuando O(k2-k1) =O(n), la complejidad general será O(n* Log n ) .
- pero en la mayoría de los casos… será menor que O(n Log n) que es igual al enfoque de clasificación descrito anteriormente.
Implementación:
C++
// C++ implementation of above approach
#include <bits/stdc++.h>
using namespace std;
int n = 7;
void minheapify(int a[], int index)
{
int small = index;
int l = 2 * index + 1;
int r = 2 * index + 2;
if (l < n && a[l] < a[small])
small = l;
if (r < n && a[r] < a[small])
small = r;
if (small != index) {
swap(a[small], a[index]);
minheapify(a, small);
}
}
int main()
{
int i = 0;
int k1 = 3;
int k2 = 6;
int a[] = { 20, 8, 22, 4, 12, 10, 14 };
int ans = 0;
for (i = (n / 2) - 1; i >= 0; i--) {
minheapify(a, i);
}
// decreasing value by 1 because we want min heapifying k times and it starts
// from 0 so we have to decrease it 1 time
k1--;
k2--;
// Step 1: Do extract minimum k1 times (This step takes O(K1 Log n) time)
for (i = 0; i <= k1; i++) {
// cout<<a[0]<<endl;
a[0] = a[n - 1];
n--;
minheapify(a, 0);
}
/*Step 2: Do extract minimum k2 – k1 – 1 times and sum all
extracted elements. (This step takes O ((K2 – k1) * Log n) time)*/
for (i = k1 + 1; i < k2; i++) {
// cout<<a[0]<<endl;
ans += a[0];
a[0] = a[n - 1];
n--;
minheapify(a, 0);
}
cout << ans;
return 0;
}
Java
// Java implementation of above approach
class GFG
{
static int n = 7;
static void minheapify(int []a, int index)
{
int small = index;
int l = 2 * index + 1;
int r = 2 * index + 2;
if (l < n && a[l] < a[small])
small = l;
if (r < n && a[r] < a[small])
small = r;
if (small != index)
{
int t = a[small];
a[small] = a[index];
a[index] = t;
minheapify(a, small);
}
}
// Driver code
public static void main (String[] args)
{
int i = 0;
int k1 = 3;
int k2 = 6;
int []a = { 20, 8, 22, 4, 12, 10, 14 };
int ans = 0;
for (i = (n / 2) - 1; i >= 0; i--)
{
minheapify(a, i);
}
// decreasing value by 1 because we want
// min heapifying k times and it starts
// from 0 so we have to decrease it 1 time
k1--;
k2--;
// Step 1: Do extract minimum k1 times
// (This step takes O(K1 Log n) time)
for (i = 0; i <= k1; i++)
{
a[0] = a[n - 1];
n--;
minheapify(a, 0);
}
for (i = k1 + 1; i < k2; i++)
{
// cout<<a[0]<<endl;
ans += a[0];
a[0] = a[n - 1];
n--;
minheapify(a, 0);
}
System.out.println(ans);
}
}
// This code is contributed by mits
Python3
# Python 3 implementation of above approach n = 7 def minheapify(a, index): small = index l = 2 * index + 1 r = 2 * index + 2 if (l < n and a[l] < a[small]): small = l if (r < n and a[r] < a[small]): small = r if (small != index): (a[small], a[index]) = (a[index], a[small]) minheapify(a, small) # Driver Code i = 0 k1 = 3 k2 = 6 a = [ 20, 8, 22, 4, 12, 10, 14 ] ans = 0 for i in range((n //2) - 1, -1, -1): minheapify(a, i) # decreasing value by 1 because we want # min heapifying k times and it starts # from 0 so we have to decrease it 1 time k1 -= 1 k2 -= 1 # Step 1: Do extract minimum k1 times # (This step takes O(K1 Log n) time) for i in range(0, k1 + 1): a[0] = a[n - 1] n -= 1 minheapify(a, 0) # Step 2: Do extract minimum k2 – k1 – 1 times and # sum all extracted elements. # (This step takes O ((K2 – k1) * Log n) time)*/ for i in range(k1 + 1, k2) : ans += a[0] a[0] = a[n - 1] n -= 1 minheapify(a, 0) print (ans) # This code is contributed # by Atul_kumar_Shrivastava
C#
// C# implementation of above approach
using System;
class GFG
{
static int n = 7;
static void minheapify(int []a, int index)
{
int small = index;
int l = 2 * index + 1;
int r = 2 * index + 2;
if (l < n && a[l] < a[small])
small = l;
if (r < n && a[r] < a[small])
small = r;
if (small != index)
{
int t = a[small];
a[small] = a[index];
a[index] = t;
minheapify(a, small);
}
}
// Driver code
static void Main()
{
int i = 0;
int k1 = 3;
int k2 = 6;
int []a = { 20, 8, 22, 4, 12, 10, 14 };
int ans = 0;
for (i = (n / 2) - 1; i >= 0; i--)
{
minheapify(a, i);
}
// decreasing value by 1 because we want
// min heapifying k times and it starts
// from 0 so we have to decrease it 1 time
k1--;
k2--;
// Step 1: Do extract minimum k1 times
// (This step takes O(K1 Log n) time)
for (i = 0; i <= k1; i++)
{
// cout<<a[0]<<endl;
a[0] = a[n - 1];
n--;
minheapify(a, 0);
}
/*Step 2: Do extract minimum k2 – k1 – 1 times
and sum all extracted elements. (This step
takes O ((K2 – k1) * Log n) time)*/
for (i = k1 + 1; i < k2; i++)
{
// cout<<a[0]<<endl;
ans += a[0];
a[0] = a[n - 1];
n--;
minheapify(a, 0);
}
Console.Write(ans);
}
}
// This code is contributed by mits
Javascript
<script>
// Javascript implementation of above approach
let n = 7;
function minheapify(a, index)
{
let small = index;
let l = 2 * index + 1;
let r = 2 * index + 2;
if (l < n && a[l] < a[small])
small = l;
if (r < n && a[r] < a[small])
small = r;
if (small != index)
{
let t = a[small];
a[small] = a[index];
a[index] = t;
minheapify(a, small);
}
}
// Driver code
let i = 0;
let k1 = 3;
let k2 = 6;
let a = [ 20, 8, 22, 4, 12, 10, 14 ];
let ans = 0;
for(i = parseInt(n / 2, 10) - 1; i >= 0; i--)
{
minheapify(a, i);
}
// decreasing value by 1 because we want
// min heapifying k times and it starts
// from 0 so we have to decrease it 1 time
k1--;
k2--;
// Step 1: Do extract minimum k1 times
// (This step takes O(K1 Log n) time)
for(i = 0; i <= k1; i++)
{
a[0] = a[n - 1];
n--;
minheapify(a, 0);
}
for(i = k1 + 1; i < k2; i++)
{
// cout<<a[0]<<endl;
ans += a[0];
a[0] = a[n - 1];
n--;
minheapify(a, 0);
}
document.write(ans);
// This code is contributed by vaibhavrabadiya117
</script>
Producción
26
La complejidad temporal general de este método es O(n + k2 Log n), que es mejor que el método basado en la clasificación.
Referencias : https://www.geeksforgeeks.org/heap-sort
Este artículo es una contribución de Nishant_Singh (Pintu) .
Método 3: (Usando Max Heap – más optimizado)
La siguiente idea utiliza la estrategia Max Heap para encontrar la solución.
Algoritmo:
- La idea es encontrar el elemento KthSmallest para K1 y K2.
- Luego simplemente recorra la array y sume los elementos Menos de K1 y Más de K2 Valor.
Ahora la idea gira en torno a KthSmallest Finding:
- El CRUX aquí es que estamos almacenando los K elementos más pequeños en el MAX Heap
- Entonces, mientras cada pulsación, si el tamaño supera K, entonces sacamos el valor Máximo.
- De esta manera después de todo el recorrido. nos quedamos con elementos K.
- Luego, el NK-ésimo elemento más grande se extrae y se entrega, que es lo mismo que el K-ésimo elemento más pequeño.
Entonces, de esta manera, podemos escribir un código funcional usando C++ STL Priority_Queue, obtenemos la solución más optimizada en tiempo y espacio.
C++
#include <bits/stdc++.h>
using namespace std;
//O(NlogK) Time to find Kth Smallest Element in Array
long long KthSmallest(long long A[], long long N, long long K){
priority_queue<long long>maxH; // MAX Heap
for(int i=0; i<N; i++){ //O(NlogK)
maxH.push(A[i]); //O(log K)
if(maxH.size()>K){
//O(log K)
maxH.pop(); //Re-heapify happens
}
}
return maxH.top();
}
long long sumBetweenTwoKth( long long A[], long long N, long long K1, long long K2){
long long K1val = KthSmallest(A,N,K1);
long long K2val = KthSmallest(A,N,K2);
//Now just traverse and sum up all vals between these above vals
long long sum = 0;
for(int i=0; i<N; i++){
if(A[i]>K1val && A[i]<K2val){
//between vals sum
sum+=A[i];
}
}
return sum;
}
int main(){
long long arr[] = { 20, 8, 22, 4, 12, 10, 14 };
long long k1 = 3, k2 = 6;
long long n = sizeof(arr) / sizeof(arr[0]);
cout << sumBetweenTwoKth(arr, n, k1, k2);
return 0;
}
Producción
26
Complejidad del tiempo:
O(N+ NLogK) = O(NLogK) (Término dominante)
Razones:
- El recorrido O(N) en la función.
- El K1th más pequeño y el K2 más pequeño – O(N*LogK)
- Como 1 inserción toma O (LogK) donde K es el tamaño de Heap.
- Como 1 Eliminación toma O (LogK) donde K es el tamaño de Heap.
Complejidad de espacio adicional:
OK)
Razones:
- Como usamos Heap / Priority Queue y solo almacenamos en max K elementos, no más que eso.
Balakrishnan R (rbkraj000 – GFG ID) contribuye con la idea, el algoritmo y el código del Método 3 anterior . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA