題目內容
題目頁面: https://app.codility.com/programmers/lessons/6-sorting/max_product_of_three/
題目理解
總之就是取得陣列A裡面，由N個數字所挑選隨意三個相乘的最大值，這些數字可能是-1000~1000，然後陣列長度最少3個最多10萬個
解題紀錄
首先我想到，形成最大值的三個值，當該值為正數時，只有可能由3個正數或2個負數*1個正數組成。當該值為負數時，則有可能由3個負數或2個正數*1個負數組成。所以，現在所需的就是先遍歷整個陣列，然後確認正數和負數的數量。當有可能有正數乘積時，則以正數乘積為優先，否則則需要考慮負數的乘積。
因此，我決定先遍歷A陣列，找尋最大的前三個正數數字以及最小的前三個負數數字(當正值時使用)，以及最小的前三個正數數字以及最大的負數數字(當負值時使用)，然後統計正值的數量和負值的數量，以決定最後輸出的會是正值還是負值
function solution(A) {
// Implement your solution here
var max_positive = new triplet(true)
var min_positive = new triplet(false)
var positive_count = 0
var max_negative = new triplet(true)
var min_negative = new triplet(false)
var negative_count = 0
var has_zero = false
for (var i = 0; i < A.length; i++) {
if (A[i] == 0) has_zero = true
else if (A[i] > 0) {
max_positive.compareMax(A[i])
min_positive.compareMin(A[i])
positive_count++
} else {
max_negative.compareMax(A[i])
min_negative.compareMin(A[i])
negative_count++
}
}
if (positive_count >= 3 || (negative_count >= 2 && positive_count > 0)) {
var pos_3 = 0
var pos_2_neg_1 = 0
if (positive_count >= 3) {
pos_3 = max_positive.max * max_positive.middle * max_positive.min
}
if (negative_count >= 2 && positive_count > 0) {
pos_2_neg_1 = min_negative.middle * min_negative.min * max_positive.max
}
return Math.max(pos_3, pos_2_neg_1)
} else if (has_zero) {
return 0
} else {
//確認該使用2個正數*1個負數還是3個負數
var max_2_pos_1_neg = -Infinity
var max_3_neg = -Infinity
if (negative_count > 0 && positive_count >= 2) {
max_2_pos_1_neg = min_positive.min * min_positive.middle * max_negative.max
}
if (negative_count >= 3) {
max_3_neg = max_negative.max * max_negative.middle * max_negative.min
}
return Math.max(max_2_pos_1_neg, max_3_neg)
}
}
class triplet {
constructor(isMaxCompare) {
var data = isMaxCompare ? -Infinity : Infinity
this.max = data;
this.middle = data;
this.min = data;
}
getValue() {
console.log(this.max, this.middle, this.min)
}
compareMax(value) {
if (value > this.max) {
this.min = this.middle
this.middle = this.max
this.max = value
} else if (value > this.middle) {
this.min = this.middle
this.middle = value
} else if (value > this.min) {
this.min = value
}
}
compareMin(value) {
if (value < this.min) {
this.max = this.middle
this.middle = this.min
this.min = value
} else if (value < this.middle) {
this.max = this.middle
this.middle = value
} else if (value < this.max) {
this.max = value
}
}
}
100%!!!一次成功~感動(https://app.codility.com/demo/results/trainingR9PVFF-P78/)
