[Codility] 第六課 MaxProductOfThree

一個不是空的陣列 A 含有 N個整數，產出的三個數字組合為 (P, Q, R)，
相乘結果為 A[P] * A[Q] * A[R] (0 < P < Q < R < N)

舉例來說，有一個 陣列 A

A[0] = -3
A[1] = 1
A[2] = 2
A[3] = -2
A[4] = 5
A[5] = 6


(0, 1, 2), 結果為 −3 * 1 * 2 = −6
(1, 2, 4), 結果為 1 * 2 * 5 = 10
(2, 4, 5), 結果為 2 * 5 * 6 = 60

所以 function 返回最大值 60，因為它是 (2, 4, 5) 的乘積最大值。

條件：

• N的範圍必須是 3~100,000
• 陣列 A 每個元素範圍 -1000,000 ~ 1000,000

複雜度：

• 最糟的時間複雜度為 O(N * log(N))
• 最糟的空間複雜度為 O(1) (不含 input 的參數)

Java 程式碼

// you can also use imports, for example:
// you can also use imports, for example:
import java.util.*;

// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");

class Solution {
    public int solution(int[] A) {
        // write your code in Java SE 8
        Arrays.sort(A);
        HashSet<Integer> set = new HashSet<Integer>();
        for(int i = 0;i < A.length; i++){
            if(!set.contains(A[i])){
                set.add(A[i]);
            }
        }
        return set.size();
    }
}

分數共拿 100%
任何問題歡迎交流討論，一起學習！

更多面試相關

⇒ [Codility] 面試寫題目經驗感想

感謝相關連結
https://www.codility.com/