下面是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