前往
大廳
主題

LeetCode - 1380. Lucky Numbers in a Matrix 解題心得

Not In My Back Yard | 2023-01-30 12:00:01 | 巴幣 0 | 人氣 127

題目連結:


題目意譯:
給定一個 m × n 的相異數字矩陣,回傳矩陣中所有的幸運數字(按任意順序)。

一個幸運數字為矩陣中的一個元素,其滿足其為同一列元素中最小者,且同時為同一行元素中最大者。

限制:
(譯者注:撰題者在這邊似乎粗心了點。以下用了 mat 和 matrix 兩個不同名稱來表示同一個參數,而兩者都代表著「輸入」的那一個矩陣)
m == mat.length
n == mat[i].length
1 ≦ n, m ≦ 50
1 ≦ matrix[i][j] ≦ 10 ^ 5.
matrix 中的所有元素彼此相異。



範例測資:
範例 1:
輸入: matrix = [[3,7,8],[9,11,13],[15,16,17]]
輸出: [15]
解釋: 15 是唯一一個幸運數字,因為它滿足其為同一列元素中最小者,且同時為同一行元素中最大者。

範例 2:
輸入: matrix = [[1,10,4,2],[9,3,8,7],[15,16,17,12]]
輸出: [12]
解釋: 12 是唯一一個幸運數字,因為它滿足其為同一列元素中最小者,且同時為同一行元素中最大者。

範例 3:
輸入: matrix = [[7,8],[1,2]]
輸出: [7]
解釋: 7 是唯一一個幸運數字,因為它滿足其為同一列元素中最小者,且同時為同一行元素中最大者。


解題思維:
把每一列各自最小值和每一行各自的最大值記錄起來,依序存成 rowMinimums 和 columnMaximums。

然後掃過一次 matrix 的每個數字 matrix[i][j],然後看 matrix[i][j] 是否恰好為 rowMinimums[i] 以及 columnMaximums[j]。如果是就代表該數字為幸運數字。

最後只要回傳「這些」幸運數字即可。



不過實際上,由於題目的條件——幸運數字為某列最小值且為某行最大值,再加上 matrix 中的數字相異,因此我們可以推得出幸運數字最多只會有一個而已(有可能會沒有,例如 [[1,4], [3,2]] 就沒有)。

因為 matrix 中的數字都不一樣,因此如果幸運數字存在的話(假設有一個在第 i 列第 j 行,其值為 X),則代表著第二個幸運數字要存在的話(假設在第 i' 列第 j' 行,其值為 X'),必須滿足下列條件:
i' ≠ i 且 j' ≠ j(顯而易見)、
X' > 第 i 列第 j' 行的數字(因為幸運數字要是該行最大值)、
X' < 第 i' 列第 j 行的數字(因為幸運數字要是該列最小值)。

而我們根據 X 的存在又知道:
第 i 列第 j' 行的數字 > X 且
第 i' 列第 j 行的數字 < X。

結合前面的條件我們便得到 X' 應 < X 且 > X,很明顯這是不可能的。因此不可能有第二個幸運數字存在。

因此在 matrix 中搜尋幸運數字的時候,只要找到一個的時候便可以直接回傳該數字(因為不用再找了)。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作