Dadas dos arrays de strings , arr1[] y arr2[] , la tarea es contar el número de strings en arr2[] cuya frecuencia de los caracteres más pequeños es menor que la frecuencia del carácter más pequeño para cada string en arr1[] .
Ejemplos:
Entrada: arr1[] = {“cbd”}, arr2[] = {“zaaaz”}
Salida: 1
Explicación:
La frecuencia de los caracteres más pequeños en “cbd” es 1, que es menor que la frecuencia de los caracteres más pequeños en “ zaaaz” que es 2.
Por lo tanto, el conteo total es 1 para la string “cbd”.Entrada: arr1[] = {“yyy”,”zz”}, arr2[] = {“x”,”xx”,”xxx”,”xxxx”} Salida: 1 2 Explicación: 1. La
frecuencia de
la
menor caracteres en «yyy» es 3, que es menor que la frecuencia de los caracteres más pequeños en «xxxx», que es 4.
Por lo tanto, el recuento total es 1 para la string «yyy».
2. La frecuencia de los caracteres más pequeños en “zz” es 2, que es menor que la frecuencia de los caracteres más pequeños en “xxx” y “xxxx”, que es 3 y 4 respectivamente.
Por lo tanto, la cuenta total es 2 para la string «zz».
Enfoque: este problema se puede resolver utilizando el enfoque codicioso . A continuación se muestran los pasos:
- Para cada string en la array, arr2[] cuenta la frecuencia de los caracteres más pequeños y los almacena en la array (por ejemplo, freq[] ).
- Ordene la array de frecuencias freq[] .
- Ahora, para cada string en la array arr1[] cuente la frecuencia de los caracteres más pequeños en la string (por ejemplo, X ).
- Para cada X , encuentre la cantidad de elementos mayores que X en freq[] mediante la búsqueda binaria utilizando el enfoque que se analiza en este artículo .
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 count the frequency of
// minimum character
int countMinFreq(string s)
{
// Sort the string s
sort(s.begin(), s.end());
// Return the count with smallest
// character
return count(s.begin(), s.end(), s[0]);
}
// Function to count number of frequency
// of smallest character of string arr1[]
// is less than the string in arr2[]
void countLessThan(vector<string>& arr1,
vector<string>& arr2)
{
// To store the frequency of smallest
// character in each string of arr2
vector<int> freq;
// Traverse the arr2[]
for (string s : arr2) {
// Count the frequency of smallest
// character in string s
int f = countMinFreq(s);
// Append the frequency to freq[]
freq.push_back(f);
}
// Sort the frequency array
sort(freq.begin(), freq.end());
// Traverse the array arr1[]
for (string s : arr1) {
// Count the frequency of smallest
// character in string s
int f = countMinFreq(s);
// find the element greater than f
auto it = upper_bound(freq.begin(),
freq.end(), f);
// Find the count such that
// arr1[i] < arr2[j]
int cnt = freq.size()
- (it - freq.begin());
// Print the count
cout << cnt << ' ';
}
}
// Driver Code
int main()
{
vector<string> arr1, arr2;
arr1 = { "yyy", "zz" };
arr2 = { "x", "xx", "xxx", "xxxx" };
// Function Call
countLessThan(arr1, arr2);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
import java.util.*;
class GFG
{
// Function to count the frequency of
// minimum character
static int countMinFreq(String s)
{
// Sort the string s
char[] tempArray = s.toCharArray();
Arrays.sort(tempArray);
s = new String(tempArray);
// Return the count with smallest
// character
int x = 0;
for (int i = 0; i < s.length(); i++)
if (s.charAt(i) == s.charAt(0))
x++;
return x;
}
// Function to count number of frequency
// of smallest character of string arr1[]
// is less than the string in arr2[]
static void countLessThan(List<String> arr1,
List<String> arr2)
{
// To store the frequency of smallest
// character in each string of arr2
List<Integer> freq = new ArrayList<Integer>();
// Traverse the arr2[]
for (String s : arr2)
{
// Count the frequency of smallest
// character in string s
int f = countMinFreq(s);
// Append the frequency to freq[]
freq.add(f);
}
// Sort the frequency array
Collections.sort(freq);
// Traverse the array arr1[]
for (String s : arr1) {
// Count the frequency of smallest
// character in string s
int f = countMinFreq(s);
// find the element greater than f
int it = upper_bound(freq, f);
// Find the count such that
// arr1[i] < arr2[j]
int cnt = freq.size() - it;
// Print the count
System.out.print(cnt + " ");
}
}
static int upper_bound(List<Integer> freq, int f)
{
int low = 0, high = freq.size() - 1;
while (low < high) {
int mid = (low + high) / 2;
if (freq.get(mid) > f)
high = mid;
else
low = mid + 1;
}
return (freq.get(low) < f) ? low++ : low;
}
// Driver Code
public static void main(String[] args)
{
List<String> arr1, arr2;
arr1 = Arrays.asList(new String[] { "yyy", "zz" });
arr2 = Arrays.asList(
new String[] { "x", "xx", "xxx", "xxxx" });
// Function Call
countLessThan(arr1, arr2);
}
}
// This code is contributed by jithin.
Python3
# Python3 program for the above approach from bisect import bisect_right as upper_bound # Function to count the frequency # of minimum character def countMinFreq(s): # Sort the string s s = sorted(s) # Return the count with smallest # character x = 0 for i in s: if i == s[0]: x += 1 return x # Function to count number of frequency # of smallest character of string arr1[] # is less than the string in arr2[] def countLessThan(arr1, arr2): # To store the frequency of smallest # character in each string of arr2 freq = [] # Traverse the arr2[] for s in arr2: # Count the frequency of smallest # character in string s f = countMinFreq(s) # Append the frequency to freq[] freq.append(f) # Sort the frequency array feq = sorted(freq) # Traverse the array arr1[] for s in arr1: # Count the frequency of smallest # character in string s f = countMinFreq(s); # find the element greater than f it = upper_bound(freq,f) # Find the count such that # arr1[i] < arr2[j] cnt = len(freq)-it # Print the count print(cnt, end = " ") # Driver Code if __name__ == '__main__': arr1 = ["yyy", "zz"] arr2 = [ "x", "xx", "xxx", "xxxx"] # Function Call countLessThan(arr1, arr2); # This code is contributed by Mohit Kumar
Javascript
<script>
// JS program for the above approach
function upper_bound(freq, f)
{
let low = 0, high = freq.length - 1;
while (low < high) {
let mid = Math.floor((low + high) / 2);
if (freq[mid] > f)
high = mid;
else
low = mid + 1;
}
return (freq[low] < f) ? low++ : low;
}
// Function to count the frequency of
// minimum character
function countMinFreq(s)
{
// Sort the string s
s = s.split('').sort().join('');
// Return the count with smallest
// character
let x = 0;
for(let i=0;i<s.length;i++){
if(s[i] == s[0])
x += 1;
}
return x;
}
// Function to count number of frequency
// of smallest character of string arr1[]
// is less than the string in arr2[]
function countLessThan(arr1,arr2)
{
// To store the frequency of smallest
// character in each string of arr2
let freq = [];
// Traverse the arr2[]
for (let i = 0;i< arr2.length;i++) {
// Count the frequency of smallest
// character in string s
let f = countMinFreq(arr2[i]);
// Append the frequency to freq[]
freq.push(f);
}
// Sort the frequency array
freq= freq.sort(function(a,b){return a-b});
// Traverse the array arr1[]
for (let i = 0;i< arr1.length;i++) {
// Count the frequency of smallest
// character in string s
let f = countMinFreq(arr1[i]);
// find the element greater than f
let it = upper_bound(freq, f);
// Find the count such that
// arr1[i] < arr2[j]
let cnt = freq.length
- (it);
// Print the count
document.write(cnt,' ');
}
}
// Driver Code
let arr1, arr2;
arr1 = [ "yyy", "zz" ];
arr2 = [ "x", "xx", "xxx", "xxxx" ];
// Function Call
countLessThan(arr1, arr2);
</script>
Producción:
1 2
Complejidad de tiempo: O(N + M*log M) , donde N y M son las longitudes de las arrays dadas, respectivamente.
Espacio Auxiliar: O(M)