-
Notifications
You must be signed in to change notification settings - Fork 0
/
matrix2d.go
93 lines (71 loc) · 1.6 KB
/
matrix2d.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
// Copyright 2018 Esote. All rights reserved. Use of this source code is
// governed by an MIT license that can be found in the LICENSE file.
package matrix2d
// Point represents a point in the matrix, indexed by row and column.
type Point struct {
X int
Y int
}
// Search searches a rectangular, sorted (column-wise and row-wise) matrix.
func Search(matrix [][]int, key int) (Point, bool) {
badpt := Point{-1, -1}
width := len(matrix)
if width < 1 {
return badpt, false
}
height := len(matrix[0])
if height < 1 {
return badpt, false
}
if height < width {
ret, ok := Search(lazyTranspose(matrix), key)
return Point{ret.Y, ret.X}, ok
}
minc := 0
maxr := height - 1
diag := height / width
for minc < width && maxr >= 0 {
r := max(maxr-diag, 0)
if e := matrix[minc][r]; key == e {
return Point{minc, r}, true
} else if key < e {
maxr = r - 1
continue
}
minrc := r + 1
maxrc := maxr
for minrc <= maxr {
mid := minrc + (maxrc-minrc+1)/2
if e := matrix[minc][mid]; key == e {
return Point{minc, mid}, true
} else if key < e {
maxrc = mid - 1
maxr = mid - 1
} else {
minrc = mid + 1
}
}
minc++
}
return badpt, false
}
// Rotate a rectangular dim0 x dim1 matrix. Assumes matrix of valid size.
func lazyTranspose(matrix [][]int) [][]int {
dim0 := len(matrix)
dim1 := len(matrix[0])
ret := make([][]int, dim1)
for i := 0; i < dim1; i++ {
ret[i] = make([]int, dim0)
for j := 0; j < dim0; j++ {
ret[i][j] = matrix[j][i]
}
}
return ret
}
// Find maximum of two integers.
func max(a, b int) int {
if a > b {
return a
}
return b
}