2148. Count Elements With Strictly Smaller and Greater Eleme

英文版點我｜中文版點我

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

❶ Sorting

排列肯定是觀察極值最快的辦法。由小到大排序後，分別從頭、尾端尋找首個「不等於極值」的位置，就能得到夾在中間的有幾項。不過排列畢竟是 nlogn 運算，而且要細心處理一些 edge case：

// 以下三種狀況都要輸出 0

[8,8,8,8,8]
[2,2,3,3]
[0]

❷ Iteration

話說回來，最大、最小值其實不靠 sorting，做個迴圈也找得到，後續再跑一圈統計介於兩者的項數就行了，也可以用 filter 完成：

// 效果等同於迴圈
return nums.filter(x=>x>min&& x<max).length;

這解法不太需要擔心邊界狀況也很直觀，只是得遍歷陣列兩次 O(2n)，假設面試官規定只能跑一次迴圈，還能怎麼做呢？

❸ Hash Table

凡出現的極值都要排除，既然如此，答案不就等於陣列長度扣掉極值出現的次數？

我們一邊找最大、最小值，一邊將出現的數字做統計，迴圈一結束也就知道極值的頻率了！索引計數用空間交換了時間，免除要重跑一次迴圈，這個做法的時間及空間複雜度都是 O(n)。

參考程式碼：

var countElements = function(nums) {
    let map={}, min=Infinity, max=-Infinity;

    for(let i=0; i<nums.length; i++){
        min=Math.min(min, nums[i]);
        max=Math.max(max, nums[i]);
        // 若 key 不存在即視為 0 次起計
        map[nums[i]]=(map[nums[i]]||0)+1;
    }
    return Math.max(0, nums.length-map[min]-map[max]);
};

為什麼第 9 行不直接 return nums.length-map[min]-map[max] 呢？這題就留給你當回家作業吧 XD

• 本題分類標籤：Array、Sorting
• 本題正解率＝59.3％

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