給定一個任意數字陣列 list,例如
15, 6, 15, 5, 15, 16
要求確認陣列中每一個數字是否都完全相同,要如何比較?
一. 直覺的方法就是逐個比較
// 固定將陣列的第一個值當作參考值
Integer check = 15;
int sumCheck = 0;
for (Integer i : list) {
if (i == check)
// 在迴圈中計數與參考值相同次數
++sumCheck;
}
// 如果計數次數等於陣列大小表示陣列裡面的值全同
if (sumCheck == list.size())
System.out.println("All the same in the array !");
else
System.out.println("Not the same !");
上面這個直覺做法,依照給定的陣列大小而言,總共做了6 + 1
次的 if判斷
(迴圈裡6次 與 最後結論1次)。
當然由於參考值就是第一個,可省去第一個的判斷
逐次比較最少也得比較 6
次
二. 空間座標比較法
回想一下「高中」
在空間座標學的
兩點相同表示距離為 0 ,兩點重合
依據這個概念,問題就變成(15, 6, 15, 5, 15, 16) 與 (15, 15, 15, 15, 15, 15)
的距離是否為 0 ?
int check = 15;
int sum = 0;
for (int i : numArray) {
// 兩點距離公式可省去開平方根動作
sum += (i-check)*(i-check);
}
if (sum == 0)
System.out.println("All the same in the array !");
else
System.out.println("Not the same !");
改變思維後,完成相同問題只需要做 1
次 if判斷
。
不過卻多了
sum += (i-check)*(i-check);
這個計算。不要懷疑,站在想偷懶的電腦角度來説:做 『加減乘除』 絕對比 『if判斷』 的工作輕鬆得多。
三. 樹狀結構
回想「大學」
計概第一次接觸到樹狀結構,雖然演算法都忘光了
好險 Java 裡內建 TreeSet
物件了
// 陣列轉換成 TreeSet 步驟
Integer[] numArray = {15, 6, 15, 5, 15, 16};
List<Integer> list = Arrays.asList(numArray);
TreeSet<Integer> treeSet = new TreeSet<Integer>(list);
// 轉換成樹狀結構後,只要判斷樹狀結構是否為單一節點即為題目所求
if (treeSet.size() == 1)
System.out.println("All the same in the array !");
else
System.out.println("Not the same !");
換成樹狀結構後,加上 Set的特性不允許重複值
,如下圖所示:
以第一個值當成『節點』,比它小的在『節點左邊』,大的在『節點右邊』。
實際印出 TreeSet 的結果也會依照上述的邏輯幫我們排列好順序:
因此如果陣列裡面的值完全相同,『僅單一節點,長不出樹來』
套用樹狀結構的思維,我們只要比較TreeSet的大小是否等於 1
便滿足題目所求!
同樣只需要做 1
次 if判斷
。
結論:
我想大部分結構化的資料在SQL
下都能被處理得服服貼貼的!
不過在NoSQL
的架構下,由於沒有預先的資料表規劃,如何去設計集合的結構數學的技巧就會派上用場了 !
對於樹狀結構的其他應用,分享前幾天看到的水管影片: