CODEWITHSUNDEEP
c++vector
Anushree Bokshe
Anushree Bokshe

Reputation: 21

Clustering example in C++

I have an increasing input vector like this {0, 1, 3, 5, 6, 7, 9} and want to cluster the inputs like this {{0, 1}, {3}, {5, 6, 7}, {9}} i.e cluster only the integers that are neighbors. The data structure std::vector<std::vector<int>> solution(const std::vector<int>& input)

Upvotes: 2

Views: 1183

Answers (1)

Quentin
Quentin

Reputation: 63124

I usually advocate for not giving away solutions, but it looks like you're getting bogged down with indices and temporary vectors. Instead, standard iterators and algorithms make this task a breeze:

std::vector<std::vector<int>> solution(std::vector<int> const &input) {
    std::vector<std::vector<int>> clusters;

    // Special-casing to avoid returning {{}} in case of an empty input
    if(input.empty())
        return clusters;

    // Loop-and-a-half, no condition here
    for(auto it = begin(input);;) {
        // Find the last element of the current cluster
        auto const last = std::adjacent_find(
            it, end(input),
            [](int a, int b) { return b - a > 1; }
        );

        if(last == end(input)) {
            // We reached the end: register the last cluster and return
            clusters.emplace_back(it, last);
            return clusters;
        }

        // One past the end of the current cluster
        auto const gap = next(last);

        // Register the cluster
        clusters.emplace_back(it, gap);

        // One past the end of a cluster is the beginning of the next one
        it = gap;
    }
}

See it live on Coliru (lame output formatting free of charge)

Upvotes: 3

Related Questions