google 笔试题

长度为 N 的整数数组，找出其中任意(N-1)个乘积最大的那一组，只能用乘法，不可以用除法。要求对算法的时间复杂度和空间复杂度作出分析，不要求写程序。

    令这 N 个数的乘积为 P，
    1) 如果 P<0，则剔除其中最大的负整数即可；
    2) 如果 P=0，
        2.1) 若这 N 个数中有且仅有一个为“0”。若其他数之积为正，则剔除“0”；否则剔除任意一个非零数；
        2.2) 若这 N 个数中至少有两个为“0”，则随便剔除一个数均可；
    3) 如果 P>0，如果有正数，则剔除其中最小的正整数即可；否则，剔除最小的负整数。

    时间复杂度：遍历数组，获得正整数个数 cp，负整数个数 cn，0 的个数 cz，需要 O(N) 时间；找被剔除的数最坏情况下需要 O(N) 时间。输出结果需要 O(N) 时间。因此，时间复杂度为 O(N)。

    空间复杂度：数组存储需要 O(N) 空间，cp, cn, cz 和被剔除的数的下标各需要 O(1) 空间。因此，空间复杂度为 O(N)。