当前仅显示指定条件回帖 [ 展开查看全部 ]
文件名称:
README.md
所在目录:
教材与参考资料 / 程序设计类 / 数据结构＆算法 / 算法 / 面试与力扣题目详解 / Leetcode题目和解答 / java-leetcode / search-a-2d-matrix
文件大小:
900.00 B
下载地址:
文本预览:
## Variant of Binary Search
We can convert this problem to binary search by convert the `2D index` to `1D index`.
### 2D to 1D
a `m * n` matrix has `m * n` values. so, it is a `0 .. (m * n - 1)` array.
a `10 * 8` matrix
```
(y)
0 1 2 3 4 5 6 7 8 9
000 001 002 003 004 005 006 007 008 009 0 (x)
010 011 012 013 014 015 016 017 018 019 1
020 021 022 023 024 025 026 027 028 029 2
030 031 032 033 034 035 036 037 038 039 3
040 041 042 043 044 045 046 047 048 049 4
050 051 052 053 054 055 056 057 058 059 5
060 061 062 063 064 065 066 067 068 069 6
070 071 072 073 074 075 076 077 078 079 7
```
Note:
* x here is from top to bottom, y is from left to right
* this is for making code to be `matrix[x][y]`
`056` is at `matrix[5][6]`
* `5 (x) = 56 / 10 (width)`
* `6 (y) = 56 % 10 (width)`
so convert index `i` to `x`, `y`:
* `x = i / width`
* `y = i % width`
We can convert this problem to binary search by convert the `2D index` to `1D index`.
### 2D to 1D
a `m * n` matrix has `m * n` values. so, it is a `0 .. (m * n - 1)` array.
a `10 * 8` matrix
```
(y)
0 1 2 3 4 5 6 7 8 9
000 001 002 003 004 005 006 007 008 009 0 (x)
010 011 012 013 014 015 016 017 018 019 1
020 021 022 023 024 025 026 027 028 029 2
030 031 032 033 034 035 036 037 038 039 3
040 041 042 043 044 045 046 047 048 049 4
050 051 052 053 054 055 056 057 058 059 5
060 061 062 063 064 065 066 067 068 069 6
070 071 072 073 074 075 076 077 078 079 7
```
Note:
* x here is from top to bottom, y is from left to right
* this is for making code to be `matrix[x][y]`
`056` is at `matrix[5][6]`
* `5 (x) = 56 / 10 (width)`
* `6 (y) = 56 % 10 (width)`
so convert index `i` to `x`, `y`:
* `x = i / width`
* `y = i % width`
点赞
回复
X