是否有std算法或其组合来查找排序数组中重复值的最长序列？

Question

功能规格

在排序数组（或向量）中找到最长的重复值序列。数组的大小预计会相对较大（最多一百万个条目）。

请查看功能齐全的演示。

预订

只是为了避免第一个优化建议：实际代码使用我的实现排序范围内的增量上限而不是

std::upper_bound

；只是不想让事情变得过于复杂。

问题

有没有一种方法可以使用一种算法（或它们的简单组合）以 C++ 标准库算法来表达这一点，以避免重新发明轮子？

我真的不喜欢这段代码，因为有两个循环和丑陋的 if-else-if，但我没有找到轻松改进它的方法。

我仍然希望一些

std

算法或它们的组合可以使这项工作变得更简单。

代码

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

std::pair<std::vector<size_t>,size_t> get_longest_ranges(auto first, auto last)
{
    ptrdiff_t max_range = 0;
    size_t amount_of_ranges = 0;
    auto it = first;

    while (it != last) {
        auto it_end = std::upper_bound(it, last, *it);

        if (max_range == it_end - it) {
            ++amount_of_ranges;
        } else if (max_range < it_end - it) {
            max_range = it_end - it;
            amount_of_ranges = 1;
        }

        it = it_end;
    }

    std::vector<size_t> ranges;
    ranges.reserve(amount_of_ranges);

    it = first;
    while (it != last) {
        auto it_end = std::upper_bound(it, last, *it);

        if (it_end - it == max_range) {
            ranges.push_back(it-first);
        }

        it = it_end;
    }

    return { ranges,  max_range };
}

int main() {
    std::vector<int> v = { 1, 1, 1, 2, 2, 2, 2, 3, 3, 4, 4, 5, 6, 6, 6, 7, 7, 7, 7 };
    auto [starts, length] = get_longest_ranges(v.begin(),v.end());

    std::cout << "Max equal elements range length = " << length;

    for (auto start : starts) {
        std::cout << "\nAt position: " << start << " Values: ";
        for (size_t i = start; i < start + length; i++) {
            std::cout << v[i] << " ";
        }
    }
}

预期结果

对于上面的代码，预期结果是：

最大相等元素范围长度= 4
位置：3 值：2 2 2 2
位置：15 值：7 7 7 7

Answer 1

您不需要传递向量两次。您只需要通过一次。对于每个元素，计算它重复的频率并记住它的位置。同时可以求出最大长度。第二个循环只需要迭代最长的序列，而不需要再次迭代整个向量。

这里派上用场的算法是

std::equal_range

。

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


int main (){
    std::vector<int> v{ 1, 1, 1, 2, 2, 2, 2, 3, 3, 4, 4, 5, 6, 6, 6, 7, 7, 7, 7 };
    auto begin = v.begin();
    auto end = v.end();
    int longest = 0;
    auto longestit = begin;
    std::map<int,std::vector<std::vector<int>::iterator>,std::greater<>> m;
    while (begin != v.end()) {
        auto res = std::equal_range(begin,end,*begin);
        int size = std::distance(res.first,res.second);
        m[size].push_back(res.first);
        if (size > longest) longest = size;
        begin = res.second;
    }
    std::cout << longest << "\n";
    for (const auto& v : m[longest]){ std::cout << *v << " "; }
}