给定n个整数的数组a以及一个数x，用分治法求x在数组中出现的次数。

一种简单的分治算法如下：

1. 如果数组a为空，则返回0。
2. 如果数组a只有一个元素，则如果这个元素等于x，则返回1，否则返回0。
3. 如果数组a有两个及以上元素，则将其分为两个部分，分别递归求解x在这两个部分中出现的次数，并将这两个部分的结果相加即可。具体分法可以选择数组的中点，也可以任意选择一个位置分开。
4. 将递归得到的结果返回。

代码实现：

def count_number(a, x):
    n = len(a)
    if n == 0:
        return 0
    elif n == 1:
        return 1 if a[0] == x else 0
    else:
        mid = n // 2
        left_count = count_number(a[:mid], x)
        right_count = count_number(a[mid:], x)
        return left_count + right_count

时间复杂度为O(nlogn)，因为每次递归都将数组分为两半，总共分logn层，每层需要O(n)的时间复杂度来遍历数组。

相关问题

请c语言实现一个归并排序算法，对给定的整数数组进行排序。归并排序采用分治法，将数组分成小段，然后递归地将其排序，最后将有序的子数组合并在一起。请按升序对数组进行排序。 输入 nums：一个包含n个整数的数组。 输出 返回一个按升序排列的数组。

下面是使用C语言实现归并排序的一个简单版本。这个函数会接受一个整数数组`nums`作为参数，并返回一个新的已排序数组。归并排序的具体过程分为两个步骤：分割（Divide）和合并（Combine）。

#include <stdio.h>
#include <stdlib.h>

// 合并两个已经排好序的数组
void merge(int arr[], int left[], int leftSize, int right[], int rightSize) {
    int i = 0, j = 0, k = 0;
    
    while (i < leftSize && j < rightSize) {
        if (left[i] <= right[j]) {
            arr[k++] = left[i++];
        } else {
            arr[k++] = right[j++];
        }
    }

    // 如果左边还有元素，直接复制过去
    while (i < leftSize) {
        arr[k++] = left[i++];
    }

    // 如果右边还有元素，直接复制过去
    while (j < rightSize) {
        arr[k++] = right[j++];
    }
}

// 归并排序函数
void mergeSort(int arr[], int size) {
    if (size > 1) {
        int mid = size / 2;
        int* left = (int*)malloc(mid * sizeof(int));
        int* right = (int*)malloc((size - mid) * sizeof(int));

        // 分割
        for (int i = 0; i < mid; i++) {
            left[i] = arr[i];
        }
        for (int i = mid; i < size; i++) {
            right[i - mid] = arr[i];
        }

        // 递归排序左右两部分
        mergeSort(left, mid);
        mergeSort(right, size - mid);

        // 合并
        merge(arr, left, mid, right, size - mid);

        free(left);
        free(right);
    }
}

// 测试归并排序
int main() {
    int nums[] = {5, 2, 9, 6, 1, 8};
    int n = sizeof(nums) / sizeof(nums[0]);

    printf("Original array: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", nums[i]);
    }
    printf("\n");

    mergeSort(nums, n);

    printf("Sorted array: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", nums[i]);
    }
    printf("\n");

    return 0;
}

当你运行这个程序，它会对`nums`数组进行归并排序，然后打印出排序后的结果。注意，这个实现使用了额外的空间来存储中间结果，如果你希望原地排序，可以修改`merge`函数。

请用C语言实现一个归并排序算法，对给定的整数数组进行排序。归并排序采用分治法，将数组分成小段，然后递归地将其排序，最后将有序的子数组合并在一起。请按升序对数组进行排序。 ### 输入 nums：一个包含n个整数的数组。 ### 输出 返回一个按升序排列的数组。

#include <stdio.h>
#include <stdlib.h>

// 归并函数，将两个已排序的数组合并成一个
void merge(int* array, int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;
    int* L = (int*)malloc(n1 * sizeof(int));
    int* R = (int*)malloc(n2 * sizeof(int));

    // 分别复制左右两部分到临时数组
    for (int i = 0; i < n1; i++)
        L[i] = array[left + i];
    for (int j = 0; j < n2; j++)
        R[j] = array[mid + 1 + j];

    // 合并临时数组到原数组
    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            array[k] = L[i];
            i++;
        } else {
            array[k] = R[j];
            j++;
        }
        k++;
    }

    // 将剩余的部分复制回原数组
    while (i < n1) {
        array[k] = L[i];
        i++;
        k++;
    }
    while (j < n2) {
        array[k] = R[j];
        j++;
        k++;
    }

    free(L);
    free(R);
}

// 归并排序函数
void mergeSort(int* array, int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;
        mergeSort(array, left, mid);   // 对左半部分排序
        mergeSort(array, mid + 1, right);  // 对右半部分排序
        merge(array, left, mid, right);     // 合并两个有序部分
    }
}

// 主函数
int* sortArray(int* nums, int size) {
    int* sortedNums = (int*)malloc(size * sizeof(int)); // 创建一个新的排序后的数组

    // 复制原始数组到新数组
    for (int i = 0; i < size; i++) {
        sortedNums[i] = nums[i];
    }

    mergeSort(sortedNums, 0, size - 1);

    return sortedNums;
}

int main() {
    int nums[] = {5, 2, 8, 4, 7};
    int size = sizeof(nums) / sizeof(nums[0]);
    int* sortedArray = sortArray(nums, size);

    printf("Sorted Array: ");
    for (int i = 0; i < size; i++) {
        printf("%d ", sortedArray[i]);
    }

    free(sortedArray);
    return 0;
}

这个程序首先创建了一个新的数组`sortedNums`，然后通过`mergeSort`函数对输入数组`nums`进行归并排序。最后，它打印出排序后的数组，并释放动态分配的内存。