【每日练习】5
题目描述
给定一个无序数组，包含正数、负数和0，要求从中找出3个数的乘积，使得乘积最大，要求时间复杂度：O(n)，空间复杂度：O(1)
输入描述:
无序整数数组A[n]输出描述:
满足条件的最大乘积示例1
输入
3 4 1 2输出
24
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
using namespace std;
/*
题目描述
给定一个无序数组，包含正数、负数和0，要求从中找出3个数的乘积，使得乘积最大，
要求时间复杂度：O(n)，空间复杂度：O(1)
输入描述:
无序整数数组A[n]
输出描述:
满足条件的最大乘积
示例1
输入
3 4 1 2
输出
24
*/
int get_inputNum(string &inputStr,vector<int > &inputData){
int sum = 0;
int flag = 0;
string::size_type i = 0;
int operatorSiganl = 1;
while(i < inputStr.size()){
if(inputStr[i] <= '9' && inputStr[i] >= '0'){
sum = sum*10 + inputStr[i] - '0';
flag = 1;
}
else if(inputStr[i] == '-'){
operatorSiganl = -1;
}
else{
if(flag == 1){
inputData.push_back(sum*operatorSiganl);
flag = 0;
sum = 0;
operatorSiganl = 1;
}
}
i++;
}
if(i == inputStr.size()){//增加二句话即使最后有一个空格也不会出0
if(flag){
inputData.push_back(sum*operatorSiganl);
}
}
return 0;
}
int get_MaxProduct(long long &product,vector<int > &positiveNum,vector<int > &negativeNum,vector<int > & zeroNum){
int productDemo = 0;
int flag = 0;
// cout << "get_MaxProduct========" << endl;
// cout << "positiveNum.size() = " << positiveNum.size() << endl;
// cout << "negativeNum.size() = " << negativeNum.size() << endl;
// cout << "zeroNum.size() = " << zeroNum.size() << endl;
if(positiveNum.size() == 0){//product <= 0,negativeNum[0]是最小的，对应的绝对只是最大的
if(zeroNum.size() == 0)
product = negativeNum[2] * negativeNum[1] * negativeNum[0];
else
product = 0;
}
else if(positiveNum.size() == 1){//只有一个正数，那么挑两个最大的负数
if(negativeNum.size() >= 2)
product = positiveNum[0] * negativeNum[1] * negativeNum[0];
else//有0存在
product = 0;
}
else{//有 >=2 个正数
if(negativeNum.size() == 0){
if(positiveNum.size() >= 3)
product = positiveNum[2]*positiveNum[1]*positiveNum[0];
else
product = 0;
}
else if(negativeNum.size() == 1){
if(positiveNum.size() >= 3)
product = positiveNum[2]*positiveNum[1]*positiveNum[0];
else if(zeroNum.size() > 0)
product = 0;
else
product = positiveNum[1]*positiveNum[0] * negativeNum[0];
}
else{//>=2
productDemo = positiveNum[0]*positiveNum[1];
flag = 2;
if(negativeNum[negativeNum.size()-1]*negativeNum[negativeNum.size()-2] > positiveNum[0]*positiveNum[1]){
productDemo = negativeNum[negativeNum.size()-1] * negativeNum[negativeNum.size()-2];
flag = 0;
}
// cout << productDemo << endl;
if(positiveNum.size() >= 3)
product = productDemo * positiveNum[flag];
else
product = negativeNum[negativeNum.size()-1] * negativeNum[negativeNum.size()-2] * positiveNum[0];
}
}
return 0;
}
/************ >0 ****************/
//case 1 : 2个负数、1个正数
//case 2 : 3个正数
/************ =0 ****************/
//case 3 : 有一个等于0
/************ <0 ****************/
//case 4 : 3个负数
//case 5 : 2个正数、一个负数
int main()
{
string inputStr;
size_t dataNum;
long long product = 0;
vector<int > inputData;
vector<int > positiveNum;
vector<int > negativeNum;
vector<int > zeroNum;
cin >> dataNum;
cin.ignore();
getline(cin,inputStr);
if(get_inputNum(inputStr,inputData))
return 0;
// cout << "dataNum = " << dataNum << endl;
// cout << "inputData = " << inputData.size() << endl;
if(inputData.size() == dataNum){
for(auto i : inputData){
if(i > 0)
positiveNum.push_back(i);
else if(i < 0)
negativeNum.push_back(i);
else
zeroNum.push_back(i);
}
sort(positiveNum.begin(),positiveNum.end(),greater<int>());
sort(negativeNum.begin(),negativeNum.end(),greater<int>());
// cout << "============== negative ===========" <<endl;
// for(auto i : negativeNum)
// cout << i << endl;
// cout << "negativeNum[0] = " << negativeNum[0] << endl;
// cout << "============== positive ===========" <<endl;
// for(auto i : positiveNum)
// cout << i << endl;
if(get_MaxProduct(product,positiveNum,negativeNum,zeroNum))
return 0;
cout << product << endl;
}
return 0;
}
应该是要大数运算了，我错了，出发点错了.....
附上参考答案：
#include<stdio.h>
#define N 10000
int main(void){
int A[N]={0};
//输入数组个数;
int n;
scanf("%d",&n);
//输入数组
for(int k=0;k<n;k++){
scanf("%d",&A[k]);
}
int m1=0,m2=0,m3=0,x1=0,x2=0;
//找到最大的三位数以及最小的两位数
for(int i=0;i<n;i++){
if(A[i]>0){
if(A[i]>m1){
m3=m2;
m2=m1;
m1=A[i];
}else if(A[i]>m2){
m3=m2;
m2=A[i];
}else if(A[i]>m1){
m3=A[i];
}
}else{
if(A[i]<x1){
x2=x1;
x1=A[i];
}else if(A[i]<x2){
x2=A[i];
}
}
}
long temp=m1*m2;
long long max=temp*m3;
temp = x1*x2;
long long max1=m1*temp;
if(max1>max)
max=max1;
printf("%lld",max);
return 0;
}