Множественный набор для определенного пользователем типа данных

Опубликовано: 30 Декабря, 2021

Вам задают Q запросов. Каждый запрос содержит целое число k и информацию о человеке, т. Е. Имя, фамилию, возраст. Для каждого запроса нам нужно вывести K-го человека среди них, если вся информация о человеке расположена в порядке возрастания.
Примечание: человек A стоит перед лицом B, если имя A лексикографически меньше, чем имя B. Но если имя такое же, мы сравниваем фамилию, а также, если фамилия такая же, то мы должны сравнить их возраст .

Дано: K всегда будет меньше или равно количеству присутствующих людей.
Примеры:

Ввод: Q = 2
        1
        аа бб 10
        2 
        Би-би-си 10
Выход :
Имя: aa
Фамилия: bb
Возраст: 10 лет

Имя: bb
Фамилия: cc
Возраст: 10 лет

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Подход: Для решения указанной выше проблемы используется приведенный ниже алгоритм.

В основном нам дается подробное описание человека с каждым запросом, и мы должны сообщить K-му человеку, если они расположены в порядке возрастания.
Базовый подход: после каждого запроса мы сортируем наш список и просто выводим информацию о k-м человеке. Но если мы решим указанную выше проблему с помощью сортировки, то временная сложность будет O (q * q * log (q)). т.е. O (qlog (q)) для сортировки каждый раз и q запросов.
Оптимизировано: мы можем улучшить временную сложность для указанной выше проблемы. Как мы знаем, вставка в мультимножество может выполняться в log (n).
Итак, просто создайте мультимножество, которое можно использовать для хранения структуры, а затем после каждого запроса просто вставьте детали человека в наш мультимножество.
Итак, это кажется лучшим подходом. Наша общая сложность будет O (q * log (q)).

 // CPP program for queries to find k-th person where
 // people are considered in lexicographic order of
 // first name, then last name, then age
 #include <bits/stdc++.h>
 using namespace std;
 
struct person {
    string firstName, lastName;
    int age;
 };
 
// operator overloading to use multiset for user
 // define data type.
 bool operator<(person a, person b)
 {
    if (a.firstName < b.firstName)
        return true ;
    else if (a.firstName == b.firstName) {
        if (a.lastName < b.lastName)
            return true ;
        else if (a.lastName == b.lastName) {
            if (a.age < b.age)
                return true ;
            else
                return false ;
        }
        else
            return false ;
    }
    else
        return false ;
 }
 
// define function for printing our output
 void print(multiset<person>::iterator it)
 {
    cout << "First name:" << it->firstName << endl;
    cout << "Last name:" << it->lastName << endl;
    cout << "Age: " << it->age << endl;
 }
 
int main()
 {
    int q = 2;
 
    // define set for structure
    multiset<person> s;
 
    // declaration of person structure
    person p;
 
    // 1st Query k=1, first-name=aa, last-name=bb, age=10;
    int k = 1;
    p.firstName = "aa" ;
    p.lastName = "bb" ;
    p.age = 10;
 
    // now insert this structure in our set.
    s.insert(p);
 
    // now find Kth smallest element in set.
    multiset<person>::iterator it;
    it = s.begin();
 
    // find kth element by increment iterator by k
    std::advance(it, k - 1);
    print(it);
 
    // 2nd Query k=2, first-name=bb, last-name=cc, age=10;
    k = 2;
    p.firstName = "bb" ;
    p.lastName = "cc" ;
    p.age = 10;
 
    // now insert this structure in our set.
    s.insert(p);
 
    // now find Kth smallest element in set.
    it = s.begin();
 
    // find kth element by increment iterator by k
    std::advance(it, k - 1);
    print(it);
    return 0;
 }

Выход:

Имя: aa
Фамилия: bb
Возраст: 10 лет
Имя: bb
Фамилия: cc
Возраст: 10 лет

Хотите учиться на лучших видео и практических задачах, ознакомьтесь с базовым курсом C ++ для базового и продвинутого уровня C ++ и курсом C ++ STL для языка и STL. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .

C++

Множественный набор для определенного пользователем типа данных

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

РЕКОМЕНДУЕМЫЕ СТАТЬИ