↑看個小廣告，支持好內容↑
從結果來看，如果能組成等差數列，整組數字必定存在公差，使得排序後相鄰兩項的差值相同。
❶ Sorting
所以直觀的解法已經出爐：我們就實地排一次，檢查每兩項的差是否唯一。一旦違反必代表無法滿足條件，複雜度 nlogn+n ≈ nlogn。
❷ Set
當然，能不排的話還是盡量避免，另一種思路是從等差數列的兩端著手，在已知最大、最小值和項數後，其實已經能推出等差數列的樣貌了：
// arr=[22,15,7,18,2]
1. 以迴圈找出數列中的最大、最小值 (22、2)。
2. 數列共有五項，公差應為 (22-2)/(5-1)=5。
3. 得到等差數列 [2,7,12,17,22]。
倘若每個數字都有出現，就能湊出一個等差數列。我們當然可以依序檢查 arr.indexOf(2)!=-1、arr.indexOf(7)!=-1 ...，但每次都要重翻陣列，更好的辦法是轉成集合 (Set)。
// 陣列是否有某個數：O(n)
arr.indexOf(x) // 有則回傳 index，否則回傳 -1
// 集合是否有某個數：O(1)
set.has(x) // true/false
參考程式碼：
var canMakeArithmeticProgression = function(arr) {
// 取得最大、最小值及公差
let min=Infinity, max=-Infinity;
for(let i=0; i<arr.length; i++){
min=Math.min(min, arr[i]);
max=Math.max(max, arr[i]);
}
let diff=(max-min)/(arr.length-1);
// 依序檢查每個數是否出現
let set=new Set(arr);
while(min<max){
min+=diff;
if(!set.has(min)){return false};
}
return true;
};
- 本題分類標籤：
Array、Sorting - 本題正解率＝
69.9％
