6

我有一个包含 24.000 个元素的大向量，例如：

(1,1,1,1,3,3,3,3,3,3,5,5,5,...etc)

我想检查一行中有多少相同的元素，例如：4-6-3..etc 我使用这个代码：

static int counter=1;
vector<int>numbers;

for(int n=0;n<numbers.size()-1;n++)
{
  if(numbers[n]==numbers[n+1])
  {
    counter++;
  }
  else if(numbers[n]!=numbers[n+1])
  {
   cout<<counter<<endl;
   counter=1;
  }
}

有没有更快的算法？

4

3 回答 3

10

@rhalbersma 基本上给了你正确的答案。作为附录，如果您想以更标准的方式重写您的算法：

#include <algorithm>
#include <vector>
#include <iterator>
#include <functional>
#include <iostream>

int main()
{
    std::vector<int> v { 1, 1, 2, 3, 3, 5, 5, 5 }; // or whatever...

    auto i = begin(v);
    while (i != end(v))
    {
        auto j = adjacent_find(i, end(v), std::not_equal_to<int>());
        if (j == end(v)) { std::cout << distance(i, j); break; }
        std::cout << distance(i, j) + 1 << std::endl;
        i = next(j);
    }
}

这是一个活生生的例子。

此外，当对向量进行排序时，这将为您提供更好的最佳情况复杂性：

#include <algorithm>
#include <vector>
#include <iterator>
#include <iostream>

int main()
{
    std::vector<int> v { 1, 1, 2, 3, 3, 5, 5, 5 }; // must be sorted...

    auto i = begin(v);
    while (i != end(v))
    {
        auto ub = upper_bound(i, end(v), *i);
        std::cout << distance(i, ub) << std::endl;
        i = ub;
    }
}

这是一个活生生的例子。

于 2013-05-08T10:58:32.463 回答
6

你的算法是O(N)及时的，这对我来说似乎是最佳的，因为你必须访问每个独特的元素进行比较。您可能仍然会在这里和那里减少几个周期，例如通过消除内部条件else()或通过打开一些编译器设置，但从算法上讲，您处于良好状态。

如果输入已经排序，您可以进行一系列二进制搜​​索。这会给您带来O(N lg N)最坏情况的复杂性，但平均情况可能会大大降低，具体取决于相等元素序列的平均长度。

顺便说一句，正如@AndyProwl 在他的回答中所显示的那样：标准库即使是这种低级算法的东西也非常棒。adjacent_find和算法具有详细记录的upper_bound复杂性，迭代器约定将保护您避免出现在您自己的代码中的边缘情况。一旦你学会了这个词汇，你就可以很容易地在你自己的例程中使用它们（当 Ranges 出现在 C++ 中时，希望它也会更容易组合它们）。

于 2013-05-08T10:39:23.910 回答
0

有一些小的优化可能会给你几毫秒：

int size = numbers.size()-1;
static int counter=1;
static int *num1 = &numbers[0];
static int *num2 = &numbers[1];
for(int n=0;n<size;n++)
{
  if(*num1==*num2) counter++;
  else
  {
   cout << counter << "\n";
   counter=1;
  }
  num1++;
  num2++;
}
cout<<counter<<endl; //Caution, this line is missing in your code!!

基本上：

  • 避免通过 id 访问向量： numbers[n] 意味着计算机必须乘以 n*sizeof(int) 并将此结果添加到 numbers。使用指针并递增它更快，这意味着只是一个添加。
于 2013-05-08T11:31:40.413 回答