Выход не то, что ожидать

Question

Вот вопрос с codewars.com

Учитывая список и число N, создайте новый список, который содержит каждое число lst не более N раз без переупорядочения. Например, если N = 2, а ввод [1,2,3,1,2,1,2,3], вы берете [1,2,3,1,2], отбрасываете следующее [1,2 ], поскольку это приведет к тому, что 1 и 2 будут в результате 3 раза, а затем - 3, что приводит к [1,2,3,1,2,3].

И вот мой код:

std::vector<int> deleteNth(std::vector<int> arr, int n)
{
   int counting = 0;
   int counting2 = 0;
   for (int i : arr)
   {
    for (int j : arr)
    {
     cout << arr.size() << "  " << counting<<"  "<<counting2<<endl;
        if (i == j) 
        {
            ++counting;
            if (counting > n) { arr.erase(arr.begin() + counting2); --counting2; }
        }

        counting2++;
    }
    counting = 0;
    counting2 = 0;
}
return arr;

Базовые тесты c в порядке. Но когда я пытаюсь их случайный тест. Это беспорядок.

Ожидается: равно [8, 32, 32, 8, 8, 26, 26, 8, 19, 26, 26, 19, 26, 26, 19, 8, 8, 19, 26, 8, 8, 19, 32, 32, 26, 50, 19, 32, 32, 32, 19] Фактические: [8, 32, 32, 8, 8, 26, 26, 8, 19, 26 , 26, 19, 26, 26, 19, 8, 8, 19, 26, 8, 8, 19, 32, 26, 50, 19, 32, 32, 19]

Answer 1

Я вижу, что у вас здесь есть две вложенные петли. Вы можете достичь того, что хотите сделать, с помощью одного l oop. Просто используйте частотный массив. Здесь я использую std::map, потому что диапазон чисел неизвестен. Если диапазон известен, вы можете использовать массив или std::vector и запустить код в O (N).

#include <iostream>
#include <vector>
#include <map>

std::vector<int> deleteNth(std::vector<int>& arr, int n)
{
    std::map<int, int> freq;
    std::vector<int> result;

    for (int number : arr)
    {
        if (freq[number] >= n)
            continue;

        result.push_back(number);
        freq[number]++;
    }

    return result;
}

int main()
{
    std::vector<int> v{ 1,2,3,1,2,1,2,3 };
    auto result = deleteNth(v, 2);

    for (int i : result)
        std::cout << i << ' ';
}

Выход:

1 2 3 1 2 3