-
Notifications
You must be signed in to change notification settings - Fork 1
/
diagonal.go
93 lines (88 loc) · 2.2 KB
/
diagonal.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
package diagonal
import "github.com/catorpilor/leetcode/utils"
func diagonalTraverse(nums [][]int) []int {
// return useHashmap(nums)
return useBucket(nums)
}
// func useBruteForce(nums [][]int) []int {
// m := len(nums)
// if m < 1 {
// return nil
// }
// if m == 1 {
// return nums[0]
// }
// n := len(nums[0])
// k := 0
// upper := m - 1 + n - 1
// var ans []int
// for k <= upper {
// for i, j := k, 0; i+j == k && i >= 0 && j <= k; i, j = i-1, j+1 {
// if m+len(nums[i])-2 > upper {
// upper = m + len(nums[i]) - 2
// }
// if j >= len(nums[i]) {
// continue
// }
// ans = append(ans, nums[i][j])
// }
// k++
// }
// return ans
// }
// time complexity O(N) N means the number of values, space complexity O(N)
func useHashmap(nums [][]int) []int {
m := len(nums)
if m < 1 {
return nil
}
if m == 1 {
return nums[0]
}
set := make(map[int][]int)
maxK := 0
for i := range nums {
for j := range nums[i] {
maxK = utils.Max(maxK, i+j)
set[i+j] = append(set[i+j], nums[i][j])
}
}
var ans []int
for k := 0; k <= maxK; k++ {
tmp := set[k]
for l, r := 0, len(tmp)-1; l < r; l, r = l+1, r-1 {
tmp[l], tmp[r] = tmp[r], tmp[l]
}
ans = append(ans, tmp...)
}
return ans
}
// useBucket time complexity O(N), space complexity O(N)
func useBucket(nums [][]int) []int {
m := len(nums)
if m < 1 {
return nil
}
if m == 1 {
return nums[0]
}
var bucket [][]int
for i := range nums {
for j := range nums[i] {
if i+j == len(bucket) {
bucket = append(bucket, []int{})
}
bucket[i+j] = append(bucket[i+j], nums[i][j])
}
}
var ans []int
maxK := len(bucket)
for k := 0; k < maxK; k++ {
// reverse
for l, r := 0, len(bucket[k])-1; l < r; l, r = l+1, r-1 {
bucket[k][l], bucket[k][r] = bucket[k][r], bucket[k][l]
}
ans = append(ans, bucket[k]...)
}
return ans
}