1502. Can Make Arithmetic Progression From Sequence (判斷能否形成等

英文版點我｜中文版點我

↑看個小廣告，支持好內容↑

從結果來看，如果能組成等差數列，整組數字必定存在公差，使得排序後相鄰兩項的差值相同。

❶ 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％

❤️ 若內容對你實用，歡迎追蹤本專題，或小額贊助支持～
⭐ 這是我的第 6 篇刷題筆記，完整解題索引看這裡 → Here