Untitled

mail@pastecode.io avatar
unknown
c_cpp
a year ago
1.7 kB
23
Indexable
Never
#include <vector>
#include <unordered_map>

std::vector<int> getMeanRankCount(const std::vector<int>& rank) {
    int n = rank.size();
    std::vector<int> count(n, 0); // To store the count of groups for each mean value
    std::unordered_map<int, int> windowSum; // To store the sum of elements in the current window

    for (int x = 1; x <= n; ++x) {
        int targetSum = x * (x + 1) / 2; // The target sum for the mean value x
        int windowStart = 0;
        int currentSum = 0;

        for (int windowEnd = 0; windowEnd < n; ++windowEnd) {
            currentSum += rank[windowEnd];
            // Shrink the window from the left until the current sum is less than the target sum
            while (currentSum > targetSum) {
                currentSum -= rank[windowStart];
                windowStart++;
            }
            // If the current sum equals the target sum, it means we have found a subarray with the desired mean
            if (currentSum == targetSum) {
                int windowSize = windowEnd - windowStart + 1;
                count[x - 1]++; // Increment the count for the current mean value x
                // If the window size is equal to x, we can't extend the window anymore, so we break the loop
                if (windowSize == x) {
                    break;
                }
            }
        }
    }
    return count;
}

int main() {
    std::vector<int> rank = {1, 2, 3, 4, 5};
    std::vector<int> result = getMeanRankCount(rank);

    // Output the result
    for (int x = 1; x <= rank.size(); ++x) {
        std::cout << "For the mean x = " << x << ", the count is " << result[x - 1] << std::endl;
    }

    return 0;
}