Рубрики

Количество строк в первом массиве, которые меньше, чем каждая строка во втором массиве

Даны два массива A [] и B [], которые состоят из N и M строк соответственно. Строка S1 считается меньшей, чем строка S2, если частота наименьшего символа в S1 меньше частоты наименьшего символа в S2 . Задача состоит в том, чтобы посчитать количество строк в A [], которые меньше, чем B [i] для каждого i .

Примеры:

Input: A[] = {“aaa”, “aa”, “bdc”}, B[] = {“cccch”, “cccd”}
Output: 3 2
“cccch” has frequency of the smallest character as 4, and all the strings
in A[] have frequencies of the smallest characters less than 4.
“cccd” has frequency of the smallest character as 3 and only “aa” and “bdc”
have frequencies of the smallest character less than 3.

Input: A[] = {“abca”, “jji”}, B[] = {“jhgkki”, “aaaa”, “geeks”}
Output: 0 2 1

Наивный подход состоит в том, чтобы взять каждую строку в B [] и затем подсчитать количество строк в A [], которое будет удовлетворять условию.

Эффективный подход состоит в том, чтобы решить это, используя бинарный поиск и некоторые предварительные вычисления, как указано ниже:

  • Изначально посчитайте частоту наименьшего символа в каждой строке и сохраните в векторе / массиве .
  • Сортировать вектор / массив в порядке возрастания.
  • Теперь для каждой строки в B [i] найдите частоту наименьшего символа.
  • Используя функцию lower_bound в C ++ или выполняя бинарный поиск в векторе / массиве, найдите число чисел, частота которого меньше частоты наименьшего символа для каждого B [i] .

Ниже приведена реализация вышеуказанного подхода:

C ++

// C ++ реализация подхода
#include <bits/stdc++.h>

using namespace std;

#define MAX 26
// Функция для подсчета количества меньших
// строки в A [] для каждой строки в B []

vector<int> findCount(string a[], string b[], int n, int m)

{

  

    // Посчитаем частоту всех символов

    int freq[MAX] = { 0 };

  

    vector<int> smallestFreq;

  

    // Итерация для всех возможных строк в A []

    for (int i = 0; i < n; i++) {

        string s = a[i];

        memset(freq, 0, sizeof freq);

  

        // Увеличиваем частоту каждого персонажа

        for (int j = 0; j < s.size(); j++) {

            freq[s[j] - 'a']++;

        }

  

        // Проверяем наименьшую частоту символа

        for (int j = 0; j < MAX; j++) {

  

            // Получить наименьшую частоту символов

            if (freq[j]) {

  

                // Вставляем его в вектор

                smallestFreq.push_back(freq[j]);

                break;

            }

        }

    }

  

    // Сортировка всех частот по наименьшим

    // символ в каждой строке

    sort(smallestFreq.begin(), smallestFreq.end());

  

    vector<int> ans;

  

    // Итерация для каждой строки в B []

    for (int i = 0; i < m; i++) {

        string s = b[i];

  

        // Хеш установлен на каждую частоту 0

        memset(freq, 0, sizeof freq);

  

        // Посчитаем частоту каждого символа

        for (int j = 0; j < s.size(); j++) {

            freq[s[j] - 'a']++;

        }

  

        int frequency = 0;

  

        // Находим частоту самого маленького символа

        for (int j = 0; j < MAX; j++) {

            if (freq[j]) {

                frequency = freq[j];

                break;

            }

        }

  

        // Подсчитать количество строк в A []

        // который имеет частоту меньшего

        // символ меньше частоты

        // меньший символ строки в B []

        int ind = lower_bound(smallestFreq.begin(),

                              smallestFreq.end(), frequency)

                  - smallestFreq.begin();

  

        // Сохраняем ответ

        ans.push_back(ind);

    }

  

    return ans;

}

  
// Функция для печати ответа

void printAnswer(string a[], string b[], int n, int m)

{

  

    // Получить ответ

    vector<int> ans = findCount(a, b, n, m);

  

    // Вывести количество строк

    // за каждый ответ

    for (auto it : ans) {

        cout << it << " ";

    }

}

  
// Код драйвера

int main()

{

    string A[] = { "aaa", "aa", "bdc" };

    string B[] = { "cccch", "cccd" };

    int n = sizeof(A) / sizeof(A[0]);

    int m = sizeof(B) / sizeof(B[0]);

  

    printAnswer(A, B, n, m);

  

    return 0;

}

Джава

// Java реализация подхода

import java.util.*;

class GFG

{

    static int MAX = 26;

      

    // Функция для подсчета количества меньших

    // строки в A [] для каждой строки в B []

    static Vector<Integer> findCount(String a[], 

                                     String b[], 

                                     int n, int m)

    {

      

        // Посчитаем частоту всех символов

        int []freq = new int[MAX];

      

        Vector<Integer> smallestFreq = new Vector<Integer>();

      

        // Итерация для всех возможных строк в A []

        for (int i = 0; i < n; i++) 

        {

            String s = a[i];

            Arrays.fill(freq, 0);

              

            // Увеличиваем частоту каждого персонажа

            for (int j = 0; j < s.length(); j++) 

            {

                freq[s.charAt(j) - 'a']++;

            }

      

            // Проверяем наименьшую частоту символа

            for (int j = 0; j < MAX; j++)

            {

      

                // Получить наименьшую частоту символов

                if (freq[j] > 0

                {

      

                    // Вставляем его в вектор

                    smallestFreq.add(freq[j]);

                    break;

                }

            }

        }

      

        // Сортировать счетчик всех частот

        // самый маленький символ в каждой строке

        Collections.sort(smallestFreq);

      

        Vector<Integer> ans = new Vector<Integer>();

      

        // Итерация для каждой строки в B []

        for (int i = 0; i < m; i++) 

        {

            String s = b[i];

      

            // Хеш установлен на каждую частоту 0

            Arrays.fill(freq, 0);

      

            // Посчитаем частоту каждого символа

            for (int j = 0; j < s.length(); j++) 

            {

                freq[s.charAt(j) - 'a']++;

            }

      

            int frequency = 0;

      

            // Находим частоту самого маленького символа

            for (int j = 0; j < MAX; j++)

            {

                if (freq[j] > 0)

                {

                    frequency = freq[j];

                    break;

                }

            }

      

            // Подсчитать количество строк в A []

            // который имеет частоту меньшего

            // символ меньше частоты

            // меньший символ строки в B []

            int [] array = new int[smallestFreq.size()];

            int k = 0;

            for(Integer val:smallestFreq)

            {

                array[k] = val;

                k++;

            }

                  

            int ind = lower_bound(array, 0

                                  smallestFreq.size(), 

                                  frequency);

      

            // Сохраняем ответ

            ans.add(ind);

        }

        return ans;

    }

      

    static int lower_bound(int[] a, int low, 

                           int high, int element)

    {

        while(low < high)

        {

            int middle = low + (high - low) / 2;

            if(element > a[middle])

                low = middle + 1;

            else

                high = middle;

        }

        return low;

    

      

    // Функция для печати ответа

    static void printAnswer(String a[], String b[],

                            int n, int m)

    {

      

        // Получить ответ

        Vector<Integer> ans = findCount(a, b, n, m);

      

        // Вывести количество строк

        // за каждый ответ

        for (Integer it : ans) 

        {

            System.out.print(it + " ");

        }

    }

      

    // Код драйвера

    public static void main(String[] args) 

    {

        String A[] = { "aaa", "aa", "bdc" };

        String B[] = { "cccch", "cccd" };

        int n = A.length;

        int m = B.length;

      

        printAnswer(A, B, n, m);

    }

}

  
// Этот код предоставлен 29AjayKumar

python3

# Python3 реализация подхода

from bisect import bisect_left as lower_bound

  

MAX = 26

  
# Функция для подсчета количества поменьше
# строк в A для каждого в B

def findCount(a, b, n, m):

  

    # Посчитайте частоту всех символов

    freq=[0 for i in range(MAX)]

  

    smallestFreq=[]

  

    # Итерация для всех возможных строк в A

    for i in range(n):

        s = a[i]

  

        for i in range(MAX):

            freq[i]=0

  

        # Увеличьте частоту каждого персонажа

        for j in range(len(s)):

            freq[ord(s[j]) - ord('a')]+= 1

  

        # Проверьте наименьшую частоту символа

        for j in range(MAX):

  

            # Получить наименьшую частоту символов

            if (freq[j]):

  

                # Вставьте его в вектор

                smallestFreq.append(freq[j])

                break

  

  

    # Сортировать все частоты наименьшего

    символ # в каждой строке

    smallestFreq=sorted(smallestFreq)

  

    ans=[]

  

    # Итерация для каждого в B

    for i in range(m):

        s = b[i]

  

        # Хэш установлен на каждую частоту 0

        for i in range(MAX):

            freq[i]=0

  

        # Подсчитайте частоту каждого символа

        for j in range(len(s)):

            freq[ord(s[j]) - ord('a')]+= 1

  

  

        frequency = 0

  

        # Найти частоту самого маленького символа

        for j in range(MAX):

            if (freq[j]):

                frequency = freq[j]

                break

  

        # Подсчитать количество строк в A

        # который имеет частоту меньшего

        # символ меньше частоты

        # меньший символ в Б

        ind = lower_bound(smallestFreq,frequency)

  

        Сохраните ответ

        ans.append(ind)

  

    return ans

  

  
# Функция для печати ответа

def printAnswer(a, b, n, m):

  

    # Получить ответ

    ans = findCount(a, b, n, m)

  

    # Распечатать количество строк

    # за каждый ответ

    for it in ans:

        print(it,end=" ")

  
# Код драйвера

  

A = ["aaa", "aa", "bdc"]

B = ["cccch", "cccd"]

n = len(A)

m = len(B)

  
printAnswer(A, B, n, m)

  
# Этот код предоставлен mohit kumar 29

C #

// C # реализация подхода

using System;

using System.Collections.Generic;    

public class GFG

{

    static int MAX = 26;

       

    // Функция для подсчета количества меньших

    // строки в A [] для каждой строки в B []

    static List<int> findCount(String []a, 

                                     String []b, 

                                     int n, int m)

    {

       

        // Посчитаем частоту всех символов

        int []freq = new int[MAX];

       

        List<int> smallestFreq = new List<int>();

       

        // Итерация для всех возможных строк в A []

        for (int i = 0; i < n; i++) 

        {

            String s = a[i];

            for (int l = 0; l < freq.Length; l++)

                freq[l]=0;

               

            // Увеличиваем частоту каждого персонажа

            for (int j = 0; j < s.Length; j++) 

            {

                freq[s[j] - 'a']++;

            }

       

            // Проверяем наименьшую частоту символа

            for (int j = 0; j < MAX; j++)

            {

       

                // Получить наименьшую частоту символов

                if (freq[j] > 0) 

                {

       

                    // Вставляем его в вектор

                    smallestFreq.Add(freq[j]);

                    break;

                }

            }

        }

       

        // Сортировать счетчик всех частот

        // самый маленький символ в каждой строке

        smallestFreq.Sort();

       

        List<int> ans = new List<int>();

       

        // Итерация для каждой строки в B []

        for (int i = 0; i < m; i++) 

        {

            String s = b[i];

       

            // Хеш установлен на каждую частоту 0

            for (int l = 0; l < freq.Length; l++)

                freq[l]=0;

       

            // Посчитаем частоту каждого символа

            for (int j = 0; j < s.Length; j++) 

            {

                freq[s[j] - 'a']++;

            }

       

            int frequency = 0;

       

            // Находим частоту самого маленького символа

            for (int j = 0; j < MAX; j++)

            {

                if (freq[j] > 0)

                {

                    frequency = freq[j];

                    break;

                }

            }

       

            // Подсчитать количество строк в A []

            // который имеет частоту меньшего

            // символ меньше частоты

            // меньший символ строки в B []

            int [] array = new int[smallestFreq.Count];

            int k = 0;

            foreach (int val in smallestFreq)

            {

                array[k] = val;

                k++;

            }

                   

            int ind = lower_bound(array, 0, 

                                  smallestFreq.Count, 

                                  frequency);

       

            // Сохраняем ответ

            ans.Add(ind);

        }

        return ans;

    }

       

    static int lower_bound(int[] a, int low, 

                           int high, int element)

    {

        while(low < high)

        {

            int middle = low + (high - low) / 2;

            if(element > a[middle])

                low = middle + 1;

            else

                high = middle;

        }

        return low;

    

       

    // Функция для печати ответа

    static void printAnswer(String []a, String []b,

                            int n, int m)

    {

       

        // Получить ответ

        List<int> ans = findCount(a, b, n, m);

       

        // Вывести количество строк

        // за каждый ответ

        foreach (int it in ans) 

        {

            Console.Write(it + " ");

        }

    }

       

    // Код драйвера

    public static void Main(String[] args) 

    {

        String []A = { "aaa", "aa", "bdc" };

        String []B = { "cccch", "cccd" };

        int n = A.Length;

        int m = B.Length;

       

        printAnswer(A, B, n, m);

    }

}
// Этот код предоставлен Принчи Сингхом

Выход:

3 2

Рекомендуемые посты:

Количество строк в первом массиве, которые меньше, чем каждая строка во втором массиве

0.00 (0%) 0 votes