Re: [閒聊] 每日LeetCode
如果用 Python 來寫的話，其實可以運用語言特性來進一步減少要做的事情。
由於 Python 的排序是 stable 的，亦即相同的元素會保有原有的順序；
而如果我們直接對陣列做排序，因為 Python 中陣列的比較是 element-wise 的，
所以如果：
1. 陣列 i 比陣列 j 的士兵還多
-> 陣列 i 的 0 會比陣列 j 早出現
-> 對 Python 的 list 排序來說，陣列 i < 陣列 j
-> 剛好是題目要的
2. 陣列 i 與陣列 j 的士兵一樣多
-> Stable
-> i 跟 j 的順序會保持原樣
-> 也符合題目要求
因此，可以直接對陣列做排序。
Code:
class Solution:
def kWeakestRows(self, mat: List[List[int]], k: int) -> List[int]:
result = [(idx, soldiers) for idx, soldiers in enumerate(mat)]
result.sort(key=lambda x: x[1])
return [i for i, v in result[:k]]
而且還可以塞成一行 XD
Code:
class Solution:
def kWeakestRows(self, mat: List[List[int]], k: int) -> List[int]:
return [i for i, v in sorted([(idx, soldiers) for idx, soldiers in
enumerate(mat)], key=lambda x: x[1])[:k]]
最後的 [:k] 要放裡面或外面都可以，但放裡面應該比較快一點。
我絕對不會說我是寫錯然後發現還是 AC，於是研究了一下才發文的 (X
※ 引述《Rushia (みけねこ的鼻屎)》之銘言：
: https://leetcode.com/problems/the-k-weakest-rows-in-a-matrix/description
: 1337. The K Weakest Rows in a Matrix
: 給你一個陣列mat[][]，mat[i][j] = 0 表示市民，1 表示士兵，給予一個數字 k
: ，如果一個列的士兵越少這個列的守備越薄弱，如果士兵一樣多比較上面的列更
: 薄弱，求出前 k 個守備薄弱的列。
: 思路:
: 1.用一個 Heap 儲存每一列的士兵數量和列編號，依照題目要求排序。
: 2.從 Heap 取出 k 個元素，把他們的編號返回即可。
: Java Code:
: ---------------------------------------------------
: class Solution {
: public int[] kWeakestRows(int[][] mat, int k) {
: PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> a[0] !=
: b[0] ? a[0] - b[0] : a[1] - b[1]);
: for (int i = 0; i < mat.length; i++) {
: int count = 0;
: for (int j = 0; j < mat[0].length; j++) {
: count += mat[i][j] == 0 ? 0 : 1;
: }
: heap.offer(new int[]{count, i});
: }
: int[] res = new int[k];
: for (int i = 0; i < k; i++) {
: res[i] = heap.poll()[1];
: }
: return res;
: }
: }
: ---------------------------------------------------
--
專注是重點，各位如果手邊有安公子的話就來一下。
-《GTA5教我的五件事》民明書局
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.240.202.11 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1695054487.A.5A9.html
推
09/19 00:29,
7月前
, 1F
09/19 00:29, 1F
→
09/19 00:33,
7月前
, 2F
09/19 00:33, 2F
推
09/19 00:47,
7月前
, 3F
09/19 00:47, 3F
→
09/19 00:56,
7月前
, 4F
09/19 00:56, 4F
推
09/19 00:56,
7月前
, 5F
09/19 00:56, 5F
討論串 (同標題文章)