牛客2018校招真题——拼多多.最大乘积—

一、题目

题目描述

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

输入描述:

无序整数数组A[n]

输出描述:

满足条件的最大乘积

示例1

输入

4
3 4 1 2

输出

二、题解思路

方法一题解思路：先建立一个一维vector向量，for循环存要输入的数组A[n]，使用sort对数组进行升序排序。分析可知，最大乘积出现在排序后数组的：
1、最后三个的乘积：n-1、n-2、n-3
2、最前面两个和最后一个的乘积：0、1、n-2
使用long long类型的目的就是三个数乘积后的结果可能会超出int或者long的存储范围，因为试过int，只能通过22%。
方法二题解思路：找出数组中的第一大、第二大、第三大的三个数和数组中的第一小和第二小的两个数，最后答案选择（第一大*第二大*第三大，第一小*第二小*第一大）中的最大者。

三、代码实现

方法一C++代码实现

注意：牛客测试用例有问题，估计是太少了，这个算法使用sort会有O（nlogn）的时间复杂度，不能满足要求，但能AC，说明牛客设置的测试数据不够严谨。

#include<bits/stdc++.h>   //万能的C++头文件，包含了基本上用到的所有头文件
using namespace std;

int main()
{
    int n;
    cin>>n;  //输入数组大小n
    vector<long long> nums(n,0); //建立大小为n的vector数组,一定要这样写，否则会发生段错误（数组越界，堆栈溢出（比如，递归调用层数太多）等情况引起）
    for(int i = 0;i<n;i++)
    {
        cin>>nums[i];   //只有上面vector那样写了，这里才可以这样写
    }
    sort(nums.begin(),nums.end());   //使用算法中的sort函数对数组进行升序排序
    long long temp1 = nums[0]*nums[1]*nums[n-1];     //前两个和最后一个相乘
    long long temp2 = nums[n-1]*nums[n-2]*nums[n-3];  //最后三个相乘
    if(temp1 >= temp2)
        cout<<temp1;
    else
        cout<<temp2;
    return 0;
}

方法二C++代码实现

/*方法二：排序找到最大的三个和最小的两个*/
#include<bits/stdc++.h>
using namespace std;

int main()
{
    int n;
    cin>>n;
    vector<long long> nums(n,0);  //存输入的数组
    long long max_1 = 1,max_2 = 1,max_3 = 1,min_1 = 1,min_2 = 1;//第一大、二大、三大、第一小、二小
    for(int i = 0;i<n;i++)
    {
        cin>>nums[i];
        if(nums[i] > max_1)
        {
            max_3 = max_2;
            max_2 = max_1;
            max_1 = nums[i];
        }
        else if(nums[i] > max_2)  //已经不满足nums[i] > max_1
        {
            max_3 = max_2;
            max_2 = nums[i];
        }
        else if(nums[i] > max_3)  //已经不满足nums[i]>max_2
        {
            max_3 = nums[i];
        }
        else if(nums[i] < min_1)  //已经不满足nums[i] > max_3
        {
            min_2 = min_1;
            min_1 = nums[i];
        }
        else if(nums[i] < min_2)   //已经不满足nums[i] < min_1
        {
            min_2 = nums[i];
        }
    }
    long long result1 = max_1*max_2*max_3;  //三个最大值相乘（第一大、二大、三大）
    long long result2 = min_1*min_2*max_1;  //两个最小值（第一小、二小）和第一大值相乘
    if(result1 > result2)
        cout<<result1;
    else
        cout<<result2;
    return 0;
}

牛客2018校招真题——拼多多.最大乘积——题解+代码实现

四、知识点

1、int、long、long long取值范围

unsigned int	0~4294967295（10位数，4e9 ，4*10^9）
int	-2147483648~2147483647（10位数，2e9， 2^31-1）
long（同int）	-2147483648~2147483647
unsigned long（同unsigned int）	0~4294967295
long long	-9223372036854775808～9223372036854775807 (19位数， 9e18 ，2^63-1）
unsigned long long	unsigned long long：0～18446744073709551615 (20位数，1e19 ， 2^64-1）

2、万能的C++笔试头文件

参考：

3、vector的使用——插入新元素和在原有的旧元素基础上进行赋值操作

向vector中添加元素：push_back（）

vector<int> nums;
for(int i = 0;i < 20; i++)
{
    nums.push_back(i);
}

注意的细节：只能对vector中已经存在的元素进行赋值（=）或者修改操作，不能对vector中不存在的元素进行赋值修改

vector<int> vec;
vec[0] = 1;  //错误！

上述就是错误的写法

在写程序的时候也出现了这样的情况，当我像这样写的时候就会报错：

#include<bits/stdc++.h>   //万能的C++头文件，包含了基本上用到的所有头文件
using namespace std;

int main()
{
    int n;
    cin>>n;  //输入数组大小n
    vector<long long> nums;   //错误的写法，这样写，cin>>nums[i]就会出错，因为vector还没有元素，更谈不上赋值操作
    for(int i = 0;i<n;i++)
    {
        cin>>nums[i];   
    }
    sort(nums.begin(),nums.end());   //使用算法中的sort函数对数组进行升序排序
    long long temp1 = nums[0]*nums[1]*nums[n-1];     //前两个和最后一个相乘
    long long temp2 = nums[n-1]*nums[n-2]*nums[n-3];  //最后三个相乘
    if(temp1 >= temp2)
        cout<<temp1;
    else
        cout<<temp2;
    return 0;
}

牛客2018校招真题——拼多多.最大乘积——题解+代码实现

因此一定要按照上面C++代码实现的方法写，即定义vector时要给出大小并且初始化

;

牛客2018校招真题——拼多多.最大乘积——题解+代码实现

一、题目

二、题解思路

三、代码实现

四、知识点

Popular Programs