Экинчи Эң көп кайталанган Сөз


Кыйынчылык деңгээли жеңил
Көп суралган Amazon GE Саламаттыкты сактоо Goldman Sachs Paytm Snapdeal UHG Optum
таштанды аркан

Саптардын ырааттуулугун эске алганда, экинчи же көп кайталанган (же көп) сөздү табуу милдети турат аркан ырааттуулукта (Эки сөздүн экинчиси эң көп кайталангандыгын эске алганда, ар дайым бир сөз болот).

мисал

киргизүү:

{"Ааа", "бб", "бб", "ааа", "ааа", в "}

Output:

Экинчи жогорку жыштыгы бар сап: bb

Негизги идея

Биз ар бир саптын жыштыгын таштанды таблицасында сактайбыз, андан кийин экинчи эң жогорку жыштыктагы сапты табуу үчүн хэш таблицасын кайталай алабыз.

Хэш стол деген эмне?

Хэш таблицасы - бул маалыматтарды ассоциативдик жол менен сактаган түзүм. Хэш-таблицаларда ачкычтар анын маанилерине ылайык келтирилет, анда ар бир баскычтын уникалдуу индекси болот. Ошентип, биз каалаган маанинин индексин билсек, анда ага жетүү абдан тез жана натыйжалуу болуп калат. Хэш таблицасы ар бир баскыч үчүн уникалдуу индексти эсептөө үчүн хэштөөнү колдонот, ошондой эле хэш код деп аталат, ал аркылуу керектүү маани табылат.
Негизги таштанды таблица эки бөлүктөн турат:

  1. Hash function
    Хэш функциясы хэширлөө үчүн колдонулат, ал биздин ачкыч-баалуулуктар түгөйүнүн индексин аныктайт. Натыйжалуу таштанды функциясын тандоо - бул жакшы таштанды таблицасын түзүүнүн чечүүчү бөлүгү. Биз ар дайым анын бир тараптуу иштешин камсыздаш керек, башкача айтканда, ачкычты таштандыдан алуу мүмкүн эмес. Дагы бир эске алуу керек, таштанды функциясы ар кандай ачкычтар үчүн бирдей таштанды кодун чыгарбайт.
  2. согуштук тизме
    Массив бардык ачкыч-маанидеги жазууларды таблицада камтыйт. Массивдин көлөмү күтүлүп жаткан маалыматтардын көлөмүнө жараша коюлушу керек.

Экинчи ирет кайталанган Сөздүн алгоритми

  1. Хэш таблицасын жарыялаңыз.
  2. Ар бир саптын жыштыгын таштанды таблицасында сактаңыз.
  3. Хэш столунун үстүнөн кайталап, экинчи эң жогорку жыштыктагы сапты табыңыз.
  4. Жипти басып чыгарыңыз.

Мисал менен түшүнүү

Киргизүү: {"aaa", "bb", "bb", "aaa", "aaa", c "}

Хэш-таблица мындайча болот:

Экинчи Эң көп кайталанган Сөз

ишке ашыруу

С ++ программасы катары менен Эң көп кайталанган экинчи сөз

#include <bits/stdc++.h>
using namespace std;
string stringWithSecondHighestFrequency(vector<string> &A)
{
    unordered_map<string, int> hash_table;
    // Store the frequency of strings in a hash table
    for (int i = 0; i < A.size(); i++)
    {
        hash_table[A[i]]++;
    }
    // Find the second highest frequency
    int max_freq = 0;
    int second_highest_freq = 0;
    for (auto ele : hash_table)
    {
        max_freq = max(max_freq, ele.second);
        if (second_highest_freq < ele.second && ele.second < max_freq)
        {
            second_highest_freq = ele.second;
        }
    }
    // Find the string with second_highest_freq
    for (auto ele : hash_table)
    {
        if (ele.second == second_highest_freq)
        {
            return ele.first;
        }
    }
}
int main()
{
    vector<string> A = {"aaa", "bb", "bb", "aaa", "aaa", "c"};
    cout << "String with second highest frequency is: " << stringWithSecondHighestFrequency(A) << endl;
    return 0;
}
String with second highest frequency is: bb

JAVA программасы катары менен Эң көп кайталанган Сөз үчүн

import java.util.*;
public class Main
{
    public static String stringWithSecondHighestFrequency(String[] A)
    {
        int n = A.length;
        HashMap<String,Integer> hash_table = new HashMap<String,Integer>();
        // Store the frequency of strings in a hash table
        for (int i = 0; i < n; i++)
        {
            Integer j = hash_table.get(A[i]); 
            hash_table.put(A[i], (j == null) ? 1 : j + 1); 
        }
        // Find the second highest frequency
        int max_freq = 0;
        int second_highest_freq = 0;
        for (Map.Entry<String,Integer> entry : hash_table.entrySet())  
        {
            max_freq = Math.max(max_freq, entry.getValue());
            if (second_highest_freq < entry.getValue() && entry.getValue() < max_freq)
            {
                second_highest_freq = entry.getValue();
            }
        }
        // Find the string with second_highest_freq
        for (Map.Entry<String,Integer> entry : hash_table.entrySet())  
        {
            if (entry.getValue() == second_highest_freq)
            {
                return entry.getKey();
            }
        }
        return "";  
    }
  public static void main(String[] args) {
      String[] A = {"aaa", "bb", "bb", "aaa", "aaa", "c"};
    System.out.println("String with second highest frequency is: "+stringWithSecondHighestFrequency(A));
  }
}


String with second highest frequency is: bb

Экинчи ирет кайталанган Сөздүн татаалдыгын талдоо

Убакыттын татаалдыгы

Векторду бир гана жолу кайталап жатабыз, ошондуктан убакыттын татаалдыгы O (N).

Космостун татаалдыгы

Биз хэш-столду жүргүзүп жатабыз, ошондуктан мейкиндиктин татаалдыгы O (N).

шилтемелер