Leetcode 74 - Search a 2D Matrix

題目

Problem#

給你一個 nxm 的矩陣，問你能不能找到 target 在哪一個行哪一列?
其中每一列都是由小到大排序的，第 $i+1$ 列的第一個大於第 $i$ 列的最後一個數字

實作複雜度限制在: $O(\log{nm})$

測資限制#

• $1 \le n, m \le 100$
• $-10^4 \le mat[i][j] \le 10^4$

想法#

因為是由小到大排序的，且題目限制在$O(\log{nm})$ 所以直覺想到二分搜
先對第一行二分搜，找到 index $i$，再對第 $i$ 列做二分搜，找到 index $j$

• 時間複雜度: $\mathcal{O}(\log{nm})$
• 空間複雜度: $\mathcal{O}(n)$

AC Code#

賞析#

• 官方題解

  • 把 nxm 的二維陣列壓成一維陣列，原本的 index $i=[0,n-1], j=[0,m-1]$ 就變成了一維的 index $k = [0, n\times{m}-1]$
  • $k$ 可以用計算算回 $i, j$ $\rightarrow i = \lfloor k / m \rfloor, j = k\ mod\ m$
  • 之後 left=0, right=n*m 直接二分搜

• 另外這題是找某個元素有沒有出現，所以二分搜可以直接寫用 if 判斷存在的簡單版

心得#

寫完才發現我 m, n 跟題目相反ww