Dada una array A[] de N elementos que consta de valores de 1 a N con duplicados, la tarea es encontrar el número total de subarreglos que contienen un número dado num exactamente K veces.
Ejemplos:
Entrada: A[] = {1, 2, 1, 5, 1}, num = 1, K = 2
Salida: 2
Explicación:
Subarreglos {1, 2, 1, 5}, {1, 2, 1}, { 2, 1, 5, 1} y {1, 5, 1} contiene 1 exactamente dos veces.Entrada: A[] = {1, 5, 3, 5, 7, 5, 6, 5, 10, 5, 12, 5}, num = 5, K = 3
Salida: 14
Enfoque ingenuo: una solución simple es generar todos los subarreglos de la array dada y contar el número de subarreglos en los que el número dado aparece exactamente K veces.
Complejidad temporal: O(N 2 ) donde N es el tamaño de la array dada.
Enfoque eficiente:
- Almacene los índices que contienen el número dado num .
- Recorra la array indices[] y calcule el número de subarreglos posibles para cada índice K.
- El número de subarreglos posibles para cualquier índice K de num es igual al
Producto de (i th index – (i-1) th index) y ((i + K) th index – (i+(K – 1)) th index)
- El conteo de todos esos subarreglos da el conteo del total de subarreglos posibles en el arreglo dado.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to count subarrays // which contains a given number // exactly K times #include <bits/stdc++.h> using namespace std; // Function to return // the count of subarrays // which contains given // number exactly K times int countSubarrays(int A[], int num, int K, int size) { // Store the indices // containing num vector<int> indices; for (int i = 0; i < size; i++) { if (A[i] == num) indices.push_back(i); } // If the occurrence of num // in the entire array // is less than K if (indices.size() < K) // No such subarrays are possible return 0; // Store the previous // index of num int prev = -1; // Store the count of // total subarrays int ans = 0; // Store the count of // subarrays for current // K occurrences int ctr = 0; for (int i = 0; i <= indices.size() - K; i++) { ctr = indices[i] - prev; if (i < indices.size() - K) { ctr *= (indices[i + K] - indices[i + K - 1]); } else { ctr *= ((size - 1) - indices[i + K - 1] + 1); } ans += ctr; prev = indices[i]; } return ans; } // Driver code int main() { int A[] = { 1, 5, 3, 5, 7, 5, 6, 5, 10, 5, 12, 5 }; int num = 5; int K = 3; int size = sizeof(A) / sizeof(int); cout << countSubarrays(A, num, K, size); return 0; }
Java
// Java program to count subarrays // which contains a given number // exactly K times import java.util.*; public class Main { // Function to return // the count of subarrays // which contains given // number exactly K times public static int countSubarrays( int A[], int num, int K, int size) { // Store the indices // containing num ArrayList<Integer> indices = new ArrayList<Integer>(); for (int i = 0; i < size; i++) { if (A[i] == num) { indices.add(i); } } if (indices.size() < K) { return 0; } // Store the previous // index of num int prev = -1; // Store the count of // total subarrays int ans = 0; // Store the count of // subarrays for current // K occurrences int ctr = 0; for (int i = 0; i <= indices.size() - K; i++) { ctr = indices.get(i) - prev; if (i < indices.size() - K) { ctr *= (indices.get(i + K) - indices.get(i + K - 1)); } else { ctr *= ((size - 1) - indices.get(i + K - 1) + 1); } ans += ctr; prev = indices.get(i); } return ans; } // Driver code public static void main(String[] args) { int A[] = { 1, 5, 3, 5, 7, 5, 6, 5, 10, 5, 12, 5 }; int num = 5; int K = 3; int size = A.length; System.out.println( countSubarrays(A, num, K, size)); } }
Python3
# Python3 program to # count subarrays which # contains a given number # exactly K times # Function to return # the count of subarrays # which contains given # number exactly K times def countSubarrays(A, num, K, size): # Store the indices # containing num indices = [] for i in range (size): if (A[i] == num): indices.append(i) # If the occurrence of num # in the entire array # is less than K if (len(indices) < K): # No such subarrays are possible return 0 # Store the previous # index of num prev = -1 # Store the count of # total subarrays ans = 0 # Store the count of # subarrays for current # K occurrences ctr = 0 for i in range (len(indices) - K + 1): ctr = indices[i] - prev if (i < len(indices) - K): ctr *= (indices[i + K] - indices[i + K - 1]) else: ctr *= ((size - 1) - indices[i + K - 1] + 1) ans += ctr prev = indices[i] return ans # Driver code if __name__ == "__main__": A = [1, 5, 3, 5, 7, 5, 6, 5, 10, 5, 12, 5] num = 5 K = 3 size = len(A) print(countSubarrays(A, num, K, size)) # This code is contributed by Chitranayal
C#
// C# program to count subarrays // which contains a given number // exactly K times using System; using System.Collections; using System.Collections.Generic; class GFG{ // Function to return the count of subarrays // which contains given number exactly K times public static int countSubarrays(int[] A, int num, int K, int size) { // Store the indices // containing num ArrayList indices = new ArrayList(); for(int i = 0; i < size; i++) { if (A[i] == num) { indices.Add(i); } } if (indices.Count < K) { return 0; } // Store the previous // index of num int prev = -1; // Store the count of // total subarrays int ans = 0; // Store the count of // subarrays for current // K occurrences int ctr = 0; for(int i = 0; i <= indices.Count - K; i++) { ctr = (int)indices[i] - prev; if (i < indices.Count - K) { ctr *= ((int)indices[i + K] - (int)indices[i + K - 1]); } else { ctr *= ((size - 1) - (int)indices[i + K - 1] + 1); } ans += ctr; prev = (int)indices[i]; } return ans; } // Driver code static public void Main() { int[] A = { 1, 5, 3, 5, 7, 5, 6, 5, 10, 5, 12, 5 }; int num = 5; int K = 3; int size = A.Length; Console.WriteLine(countSubarrays(A, num, K, size)); } } // This code is contributed by akhilsaini
Javascript
<script> // JavaScript program to count subarrays // which contains a given number // exactly K times // Function to return the count of subarrays // which contains given number exactly K times function countSubarrays(A, num, K, size) { // Store the indices // containing num let indices = []; for(let i = 0; i < size; i++) { if (A[i] == num) { indices.push(i); } } if (indices.length < K) { return 0; } // Store the previous // index of num let prev = -1; // Store the count of // total subarrays let ans = 0; // Store the count of // subarrays for current // K occurrences let ctr = 0; for(let i = 0; i <= indices.length - K; i++) { ctr = indices[i] - prev; if (i < indices.length - K) { ctr *= (indices[i + K] - indices[i + K - 1]); } else { ctr *= ((size - 1) - indices[i + K - 1] + 1); } ans += ctr; prev = indices[i]; } return ans; } // Driver Code let A = [ 1, 5, 3, 5, 7, 5, 6, 5, 10, 5, 12, 5 ]; let num = 5; let K = 3; let size = A.length; document.write(countSubarrays(A, num, K, size)); </script>
14
Complejidad de tiempo: O(N) , donde N es el tamaño de la array.
Complejidad espacial: O(N)
Publicación traducida automáticamente
Artículo escrito por divyeshrabadiya07 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA