Vector - значение с k-вхождениями первым

Question

Это мой первый пост и надеюсь, что я не делаю ничего плохого. Я пытаюсь написать программу, которая находит первое значение вектора, которое достигает в нем k-вхождений.

Например, учитывая этот вектор и k = 3:

1 1 2 3 4 4 2 2 1 3

Я бы увидел 2 как вывод, потому что 2 - это первое число, достигшее 3-го вхождения.

Следующий код - это то, что я пытался запустить, но как-то вывод Неправильно.

---

    #include<iostream>
    #include<vector>

    using namespace std;

    int main()
    {

        vector<int> vettore;
        int k;
        int a,b,i;
        int occ_a;
        int occ_b;

        cout<< "Write values of vector (number 0 ends the input of values)\n"; 
        int ins;
        cin>>ins;
        while(ins)
        {
            vettore.push_back(ins);     //Elements insertion
            cin>>ins;
        }
        cout<<"how many occurrences?\n"<<endl;;
        cin>>k;
        if(k>0)
        {
            int i=0;
            b = vettore[0];
            occ_b=0;

            while(i< vettore.size())
            {

                    int j=i;
                    occ_a = 0;
                    a = vettore[i];
                    while(occ_a < k && j<vettore.size())
                    {
                        if(vettore[j]== a)
                        {
                            occ_a++;
                            vettore.erase(vettore.begin() + j);
                        }
                        else
                            j++;
                    }
                    if(b!=a && occ_b < occ_a)
                        b = a;
                    i++;

            }
            cout << b;   //b is the value that reached k-occurrences first
        }
        return 0;
    }

---

Часы прошли, но я не смог ее решить.

Спасибо за помощь!

Answer 1

Ваш код трудно читать, потому что вы объявляете переменные там, где они не используются. Поэтому их значения трудно понять.

Также нет необходимости удалять элементы из вектора. Найти значение, которое является первым, которое встречается k-раз, не эквивалентно изменению вектора. Это две разные задачи.

Я могу предложить следующее решение, показанное в демонстрационной программе ниже.

#include <iostream>
#include <vector>

int main() 
{
    std::vector<int> v = { 1, 1, 2, 3, 4, 4, 2, 2, 1, 3 };
    size_t least_last = v.size();
    size_t k = 3;

    for ( size_t i = 0; i + k <= least_last; i++ )
    {
        size_t count = 1;
        size_t j = i;

        while ( count < k && ++j < least_last )
        {
            if ( v[j] == v[i] ) ++count;
        }

        if ( count == k ) 
        {
            least_last = j;
        }           
    }

    if ( least_last != v.size() ) std::cout << v[least_last] << '\n';

    return 0;
}.

Вывод программы:

2

Идея состоит в том, найти последнюю позицию первого элемента, встречающегося k раз. Как только он будет найден, верхний предел пройденной последовательности будет установлен на это значение. Таким образом, если есть другой элемент, который встречается k раз перед этим пределом, то это означает, что он встречается первым по сравнению с уже найденным элементом.