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

一、题目


题目描述

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

输入描述:

无序整数数组A[n]

输出描述:

满足条件的最大乘积

示例1

输入

4
3 4 1 2

输出

24

二、题解思路


  • 方法一题解思路:先建立一个一维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时要给出大小并且初始化

;