【python-校园面试题】拼多多，最大乘积？

题目：给定一个无序数组，包含正数、负数和0，要求从中找出3个数的乘积，使得乘积最大，要求时间复杂度：O(n)，空间复杂度：O(1)。

分析：

最大乘积只有三种情况

1.最大的三个数相乘

2.最小的三个数相乘（全是负数的情况） ，

3.最小的两个负数再乘以最大的正数

从这三种中取最大的即可

二路归并排序的过程需要进行logn次。每一趟归并排序的操作，就是将两个有序子序列进行归并，而每一对有序子序列归并时，记录的比较次数均小于记录的移动次数，记录移动的菜属等于文件中你记录的个数n，即每一趟归并的时间复杂度为O(n)。因此二路归并排序在最好、最坏和平均情况的时间复杂度为O(nlogn)，而且是一种稳定的排序方法，空间复杂度为O(1).

基本思路： 用选择排序的思路找到最大的3个数和最小的3个数 时间复杂度O(6n)

code:

def mergeSort(A):

    if len(A) <= 1:

        return A

    # 把数组分成两部分分别排序

    half = int(len(A) / 2)

    first = mergeSort(A[0:half])

    second = mergeSort(A[half:len(A)])

    # 把两部分合并

    i = 0

    j = 0

    newA = []

    while i < len(first) or j < len(second):

        if i < len(first) and j < len(second):

            if first[i] <= second[j]:

                newA.append(first[i])

                i += 1

            else:

                newA.append(second[j])

                j += 1

        else:

            # 如果后半部数组已经全部插入，那么把前半部剩余元素插入新数组

            if i < len(first):

                newA.append(first[i])

                i += 1

            # 如果前半部数组已经全部插入，那么把后半部剩余元素插入新数组

            if j < len(second):

                newA.append(second[j])

                j += 1

    return newA

if __name__ == "__main__":

    A = [3, 1, 5, 6, 7, 4, 2, 8]

    B = [-1, -4, -2, -8, -4, -5, -54]

    C = [-1, -4, -6, -9, -10, 10, 2, 5, 67]

    A = mergeSort(A)

    B = mergeSort(B)

    C = mergeSort(C)

    #print(mergeSort(A))

    #print(mergeSort(B))

    #print(mergeSort(C))

    if len(A)< 3:

        print(0)

    else:

        print(max(A[0] * A[1] * A[-1], A[-1]*A[-2]*A[-3], A[0]*A[1]*A[2]))

        print(max(B[0] * B[1] * B[-1], B[-1]*B[-2]*B[-3], B[0]*B[1]*B[2]))

        print(max(C[0] * C[1] * C[-1], C[-1]*C[-2]*C[-3], C[0]*C[1]*C[2]))

程序运行结果：

336

-8

6030