Ini pertanyaan dari codewars.com

Diberikan daftar dan nomor N, buat daftar baru yang berisi setiap nomor pertama paling banyak N kali tanpa menyusun ulang. Misalnya jika N = 2, dan inputnya adalah [1,2,3,1,2,1,2,3], ambil [1,2,3,1,2], jatuhkan berikutnya [1,2 ] karena ini akan menyebabkan 1 dan 2 berada di hasil 3 kali, dan kemudian mengambil 3, yang mengarah ke [1,2,3,1,2,3].

Dan ini kode saya:

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;

Tes dasar baik-baik saja. Tetapi ketika saya mencoba tes acak mereka. Ini berantakan.

Diharapkan: sama dengan [ 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] Sebenarnya: [ 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 ]

-1
newbie 19 April 2020, 18:27

1 menjawab

Jawaban Terbaik

Saya melihat bahwa Anda memiliki dua loop bersarang di sini. Anda dapat mencapai apa yang ingin Anda lakukan dengan satu putaran. Cukup gunakan array frekuensi. Disini saya menggunakan std::map karena range angka tidak diketahui. Jika rentang diketahui, Anda dapat menggunakan larik atau std::vector dan menjalankan kode dalam 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 << ' ';
}

Keluaran:

1 2 3 1 2 3
0
StackExchange123 19 April 2020, 15:38