产出与预期不符

下面是codewars.com的一个问题。

给定一个列表和一个数字N,创建一个新的列表,它最多包含N次lst的每个数字,而不重新排序。例如,如果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;

基本的测试是好的。但是,当我尝试他们的随机测试, 这是一个烂摊子。

预期:等于 [ 8, 32, 32, 8, 8, 26, 26, 8, 19, 26, 26, 19, 26, 19, 8, 8, 19, 32, 32, 26, 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, 26, 8, 8, 19, 32, 26, 50, 19, 32, 32, 19 ] 。

解决方案:

我看到你这里有两个嵌套循环。你可以用一个循环来实现你想要做的事情。只要用一个频率数组就可以了。这里我使用的是 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

给TA打赏
共{{data.count}}人
人已打赏
解决方案

如何计算经过的时间 Python [关闭]

2022-4-21 19:09:29

解决方案

Sping整合邮件闲置接收的问题

2022-4-21 19:09:31

0 条回复 A文章作者 M管理员
    暂无讨论,说说你的看法吧
个人中心
购物车
优惠劵
今日签到
有新私信 私信列表
搜索