分治法求解序列中某数字的出现次数代码c++

分治法是一种常用的算法设计技巧，通过将问题分解为更小的子问题来解决原问题。在求解序列中某数字的出现次数的问题中，可以利用分治法递归地在子序列中查找该数字的出现次数，然后合并子序列的结果。

以下是一个使用C++编写的分治法求解序列中某数字出现次数的示例代码：

#include <iostream>
#include <vector>

// 定义函数原型
int countOccurrences(const std::vector<int>& arr, int start, int end, int x);

int main() {
    // 示例数组
    std::vector<int> arr = {1, 3, 2, 4, 3, 3, 5, 1};
    int x = 3; // 需要查找的数字

    // 调用函数并输出结果
    int count = countOccurrences(arr, 0, arr.size() - 1, x);
    std::cout << "The number " << x << " appears " << count << " times in the array." << std::endl;

    return 0;
}

// 分治法求解序列中某数字出现次数的函数实现
int countOccurrences(const std::vector<int>& arr, int start, int end, int x) {
    if (start > end) {
        return 0;
    }

    int mid = start + (end - start) / 2;

    // 递归查找左右子序列中的出现次数
    int leftCount = countOccurrences(arr, start, mid - 1, x);
    int rightCount = countOccurrences(arr, mid + 1, end, x);

    // 合并子序列的结果
    int count = leftCount + rightCount;

    // 计算中间位置的元素个数
    for (int i = mid; i >= start && arr[i] == x; --i) count++;
    for (int i = mid + 1; i <= end && arr[i] == x; ++i) count++;

    return count;
}

在这个例子中，`countOccurrences`函数递归地将数组`arr`分为左右两部分，直到子数组只有一个元素或为空，然后通过累加左右子数组中的出现次数，以及合并中间位置的连续出现次数来计算整个数组中数字`x`的出现次数。