排序作為一種基本算法，已經不太可能直接作為面試題，但是 以排序作為基礎內核來解決問題仍然是一個不錯的出題點 。Leetcode Q1329 就是一個很好的例子，難度並不大，卻可以很好地檢查開發者運用基礎的排序算法解決問題的能力。這遠比手動寫一個大頂堆或者紅黑樹有意義得多，畢竟真實工作中大家不太可能這樣做。
1. 題目 Q1329 矩陣對角線排序
給定一個 整數矩陣，按從左上角到右下角的 升序對角 對其進行排序，然後返回排序後的數組。
約束條件：
<code>(a) m == mat.length
(b) n == mat[i].length
(c) 1 <= m, n <= 100
(d) 1 <= mat[i][j] <= 100/<code>
示例1
<code>Input: mat = [[3,3,1,1],[2,2,1,2],[1,1,1,2]]
Output: [[1,1,1,1],[1,2,2,2],[1,2,3,3]]/<code>
解釋：
示例
2. 解題思路
題意已經描述地很清楚了，就是每個對角線單獨進行升序的排序。不過我們需要知道一點，即矩陣並不一定就是方陣。我們可以 逐個取出對角線元素，然後針對這些元素使用快速排序算法按升序排列，最後再將排序完成的元素回填到矩陣之中的對應位置處。
對角線排序示意圖
按照這個思路，排序已經不是難點了，真正的難點變成了按照對角線取元素和回填元素。從實現的角度來看，對左上角的對角線和右下角的對角線提取元素的方式還稍有差別，因此需要分開處理。
左上和右下對角線分開處理
3. C++解決方案
按照以上的思路，這裡給出C++的解決方案。
C++解決方案
在實現上需要說明的是，儘量減少零時變量的創建次數，儘量預先使用reserve()函數為vector分配內存。對於“前++”和“後++”這兩種語法的使用可以使代碼更簡潔，如果解決可讀性下降，也可以拆分開編寫。
----------------------
題外：
頻道資源，可以私信關鍵字獲取。
Python編程問題諮詢，請發送關鍵字【諮詢】
獲取leetcode源代碼，請發送關鍵字【leetcode】
獲取書籍，請發送關鍵字【書籍】
分享到:
閱讀更多 青衣極客 的文章
