Java 簡單算法：找出數組中非最大非最小元素 —— 排序後取中間值

問題描述

給定一個整型數組，找出**既不是最大值也不是最小值**的任意一個元素。原代碼嘗試單次遍歷比較相鄰三元素，邏輯極其複雜且錯誤百出。

最簡解法：排序 + 掐頭去尾

public static Integer findNonMaxNonMin(int[] arr) {
    if (arr == null || arr.length < 3) {
        return null; // 少於 3 個元素無解
    }
    Arrays.sort(arr); // 升序排序
    // arr[0] 是最小，arr[arr.length-1] 是最大
    // 返回任意中間元素，如中間位置
    return arr[arr.length / 2]; 
}

// 測試
public static void main(String[] args) {
    int[] arr = {2, 4, 6, 1, 7, 5, 3, 8};
    System.out.println(findNonMaxNonMin(arr)); // 輸出如 4 或 5 (排序後中間值)
}

進階：不改動原數組、O(n) 單次遍歷 (面試常考)

public static Integer findNonMaxNonMinOnePass(int[] arr) {
    if (arr == null || arr.length < 3) return null;
    
    int min = Integer.MAX_VALUE;
    int max = Integer.MIN_VALUE;
    
    // 1. 找出最小值和最大值
    for (int num : arr) {
        if (num < min) min = num;
        if (num > max) max = num;
    }
    
    // 2. 再次遍歷找第一個不等於 min 且不等於 max 的元素
    for (int num : arr) {
        if (num != min && num != max) {
            return num;
        }
    }
    return null; // 所有元素相同或只有兩種值
}

方案對比

原代碼錯誤分析

• 邏輯試圖通過比較相鄰三元素 (arr[i], arr[i+1], arr[i+2]) 判斷中間值，**但數組無序，相鄰元素無大小關係**，完全失效。
• 循環條件 i < arr.length - 2 會漏檢最後兩個元素。
• 多層 if-else 覆蓋不全所有排列組合。

總結

「排序之後掐頭去尾，然後隨機選一個」 是解決此問題**最簡潔、最不易出錯、工程上最推薦**的方法。除非面試強制要求 O(n) 不修改數組，否則直接 Arrays.sort() 取中間值，代碼可讀性、維護性、正確性全優。