面试题：C语言指针数组在函数参数中的复杂应用及优化

Question

假设有一个函数，其参数是一个指针数组，指针数组中的每个指针指向一个包含整数的数组。函数需要对这些整数数组进行一系列操作：1. 检查每个数组中的元素是否都为偶数，如果有奇数，则将该数组中所有元素翻倍。2. 统计所有数组中元素值大于100的个数。3. 找到元素总和最大的数组并返回其指针。请用C语言高效地实现该函数，并且分析你的实现的时间复杂度和空间复杂度，考虑如何优化。

Answer 1

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

// 定义函数，参数为指针数组，每个指针指向一个整数数组
int* performOperations(int** arrays, int numArrays, int* lengths) {
    int count = 0;
    int maxSum = 0;
    int* maxArray = NULL;

    for (int i = 0; i < numArrays; i++) {
        int hasOdd = 0;
        int sum = 0;

        // 检查数组中是否有奇数，并计算总和
        for (int j = 0; j < lengths[i]; j++) {
            if (arrays[i][j] % 2 != 0) {
                hasOdd = 1;
            }
            sum += arrays[i][j];
        }

        // 如果有奇数，将数组中所有元素翻倍
        if (hasOdd) {
            for (int j = 0; j < lengths[i]; j++) {
                arrays[i][j] *= 2;
            }
        }

        // 统计元素值大于100的个数
        for (int j = 0; j < lengths[i]; j++) {
            if (arrays[i][j] > 100) {
                count++;
            }
        }

        // 找到元素总和最大的数组
        if (sum > maxSum) {
            maxSum = sum;
            maxArray = arrays[i];
        }
    }

    // 打印统计结果
    printf("元素值大于100的个数: %d\n", count);

    return maxArray;
}

时间复杂度分析

1. 外层循环遍历 numArrays 次，每次循环中有三个内层循环，分别遍历数组的长度 lengths[i]。
2. 第一个内层循环检查奇数，时间复杂度为 $O(\sum_{i = 0}^{numArrays - 1} lengths[i])$。
3. 第二个内层循环翻倍奇数，最坏情况下（所有数组都有奇数），时间复杂度为 $O(\sum_{i = 0}^{numArrays - 1} lengths[i])$。
4. 第三个内层循环统计大于100的元素，时间复杂度为 $O(\sum_{i = 0}^{numArrays - 1} lengths[i])$。
5. 总体时间复杂度为 $O(\sum_{i = 0}^{numArrays - 1} lengths[i])$，如果所有数组长度相同，设为 $n$，则时间复杂度为 $O(numArrays * n)$。

空间复杂度分析

1. 除了输入的数组，只使用了常数级别的额外空间，如 count、maxSum、maxArray 等变量。
2. 空间复杂度为 $O(1)$。

优化

1. 减少内层循环次数：可以在第一次遍历数组时，同时完成检查奇数、计算总和以及统计大于100的元素，这样可以将内层循环次数从3次减少到1次，在一定程度上提高效率。

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

// 定义函数，参数为指针数组，每个指针指向一个整数数组
int* performOperations(int** arrays, int numArrays, int* lengths) {
    int count = 0;
    int maxSum = 0;
    int* maxArray = NULL;

    for (int i = 0; i < numArrays; i++) {
        int hasOdd = 0;
        int sum = 0;

        // 同时检查奇数、计算总和以及统计大于100的元素
        for (int j = 0; j < lengths[i]; j++) {
            if (arrays[i][j] % 2 != 0) {
                hasOdd = 1;
            }
            sum += arrays[i][j];
            if (arrays[i][j] > 100) {
                count++;
            }
        }

        // 如果有奇数，将数组中所有元素翻倍
        if (hasOdd) {
            for (int j = 0; j < lengths[i]; j++) {
                arrays[i][j] *= 2;
            }
        }

        // 找到元素总和最大的数组
        if (sum > maxSum) {
            maxSum = sum;
            maxArray = arrays[i];
        }
    }

    // 打印统计结果
    printf("元素值大于100的个数: %d\n", count);

    return maxArray;
}

这种优化后的实现，时间复杂度依然是 $O(\sum_{i = 0}^{numArrays - 1} lengths[i])$，但实际运行效率会有所提升，因为减少了内层循环的执行次数。空间复杂度仍然为 $O(1)$。