-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy path1329.py
More file actions
129 lines (118 loc) · 9.78 KB
/
1329.py
File metadata and controls
129 lines (118 loc) · 9.78 KB
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
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Time : 2020/5/7 13:49
# @Author : Fhh
# @File : 1329.py
# Good good study,day day up!
"""给你一个 m * n 的整数矩阵 mat ，请你将同一条对角线上的元素（从左上到右下）按升序排序后，返回排好序的矩阵。
示例 1：
输入：mat = [[3,3,1,1],[2,2,1,2],[1,1,1,2]]
输出：[[1,1,1,1],[1,2,2,2],[1,2,3,3]]
提示：
m == mat.length
n == mat[i].length
1 <= m, n <= 100
1 <= mat[i][j] <= 100
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/sort-the-matrix-diagonally
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
"""
from typing import List
class Solution:
def diagonalSort(self, mat: List[List[int]]) -> List[List[int]]:
if not mat or len(mat) == 1 or len(mat[0]) == 1:
return mat
def sortdia(i, j, mat):
"从mat[i][i]开始往右下对该斜线上的元素递增排序"
for a in range(i, len(mat)):
for b in range(a + 1, len(mat)):
if 0 <= a + j - i < len(mat[0]) and 0 <= b + j - i < len(mat[0]):
if mat[a][a + j - i] > mat[b][b + j - i]:
mat[a][a + j - i], mat[b][b + j - i] = mat[b][b + j - i], mat[a][a + j - i]
for i in range(len(mat)):
sortdia(i, 0, mat)
for j in range(1, len(mat[0])):
sortdia(0, j, mat)
return mat
s = Solution()
for i in s.diagonalSort(
[[3, 97, 72, 77, 16, 76, 51, 22, 80, 76, 84, 35, 20, 68, 97, 25, 86, 80, 39, 22, 79, 20, 15, 78, 35, 68, 10, 97,
5, 44, 9, 49, 19, 9, 70, 63, 89, 84, 66, 31, 29, 33, 51, 24, 60, 66, 69, 9, 80, 15],
[34, 65, 90, 21, 94, 21, 10, 16, 88, 56, 87, 43, 50, 27, 32, 86, 25, 19, 100, 89, 52, 87, 22, 26, 45, 32, 73,
51, 43, 22, 88, 7, 98, 74, 49, 19, 61, 23, 100, 68, 8, 29, 27, 91, 2, 24, 54, 65, 18, 90],
[88, 37, 76, 10, 38, 29, 54, 100, 46, 86, 71, 87, 94, 21, 91, 73, 56, 61, 25, 27, 91, 42, 91, 63, 96, 8, 98,
19, 91, 38, 61, 77, 81, 55, 8, 40, 35, 50, 91, 86, 28, 73, 72, 82, 33, 6, 9, 31, 49, 81],
[27, 45, 25, 82, 45, 52, 26, 47, 97, 20, 58, 82, 73, 23, 76, 24, 96, 65, 97, 14, 94, 84, 50, 15, 51, 41, 50,
66, 67, 12, 44, 64, 94, 9, 74, 22, 97, 80, 43, 75, 32, 40, 3, 9, 13, 75, 14, 71, 76, 25],
[39, 75, 92, 20, 20, 7, 30, 80, 84, 30, 3, 24, 39, 77, 9, 12, 2, 11, 99, 79, 32, 45, 53, 90, 52, 24, 47, 85,
27, 49, 64, 77, 83, 72, 99, 91, 1, 70, 72, 38, 34, 18, 22, 69, 49, 34, 36, 20, 11, 55],
[39, 20, 86, 28, 91, 11, 8, 94, 57, 79, 51, 91, 20, 12, 88, 43, 52, 31, 69, 23, 90, 25, 10, 36, 15, 75, 18, 42,
60, 32, 74, 15, 24, 58, 55, 88, 60, 24, 54, 18, 88, 7, 94, 22, 53, 21, 91, 51, 100, 28],
[24, 90, 100, 44, 67, 10, 53, 77, 12, 51, 77, 81, 11, 6, 52, 10, 30, 71, 40, 21, 62, 23, 61, 95, 22, 30, 97,
19, 56, 72, 40, 70, 51, 20, 61, 59, 56, 85, 13, 8, 10, 38, 62, 18, 71, 38, 6, 30, 76, 16],
[52, 16, 65, 15, 76, 88, 59, 26, 78, 81, 74, 79, 14, 81, 25, 7, 40, 23, 51, 68, 34, 41, 49, 15, 90, 78, 7, 53,
87, 46, 73, 33, 35, 19, 83, 49, 5, 70, 95, 91, 10, 78, 54, 18, 2, 34, 80, 7, 90, 65],
[24, 65, 37, 62, 12, 45, 25, 47, 42, 26, 59, 49, 9, 37, 35, 97, 3, 22, 41, 67, 84, 14, 71, 58, 35, 21, 98, 35,
74, 83, 88, 81, 95, 40, 82, 85, 99, 11, 12, 86, 90, 86, 31, 70, 42, 8, 89, 42, 85, 29],
[58, 34, 51, 78, 70, 85, 45, 95, 27, 60, 69, 46, 32, 65, 37, 83, 32, 86, 39, 91, 74, 9, 84, 36, 16, 78, 41, 84,
68, 87, 84, 15, 53, 50, 24, 8, 72, 41, 24, 5, 37, 43, 1, 85, 54, 16, 65, 97, 85, 91],
[87, 36, 70, 36, 73, 94, 62, 72, 8, 85, 62, 16, 13, 7, 64, 21, 43, 53, 64, 86, 97, 16, 50, 36, 83, 72, 38, 89,
63, 60, 15, 1, 95, 54, 1, 90, 88, 66, 14, 79, 84, 41, 40, 12, 40, 73, 69, 5, 74, 69],
[68, 84, 26, 89, 20, 19, 34, 66, 64, 15, 73, 6, 49, 38, 30, 48, 81, 62, 39, 77, 71, 67, 75, 53, 12, 41, 8, 31,
97, 2, 18, 58, 85, 51, 45, 31, 41, 14, 51, 80, 2, 78, 5, 13, 4, 48, 33, 74, 100, 20],
[19, 88, 12, 78, 47, 79, 16, 49, 28, 81, 78, 64, 50, 5, 84, 53, 48, 81, 97, 58, 8, 32, 36, 12, 16, 85, 17, 17,
91, 5, 95, 4, 55, 72, 19, 98, 31, 42, 46, 82, 99, 15, 94, 74, 91, 41, 85, 81, 13, 78],
[12, 75, 58, 70, 30, 96, 99, 53, 26, 27, 90, 40, 59, 5, 16, 71, 15, 2, 55, 31, 88, 45, 11, 91, 47, 51, 53, 36,
43, 4, 9, 94, 19, 33, 14, 86, 94, 82, 12, 4, 44, 18, 49, 5, 100, 24, 23, 48, 53, 7],
[94, 75, 58, 44, 81, 53, 4, 42, 87, 38, 76, 3, 21, 81, 92, 42, 78, 25, 90, 33, 68, 24, 72, 2, 90, 97, 25, 18,
61, 16, 50, 4, 88, 80, 72, 7, 94, 96, 23, 92, 92, 48, 80, 24, 71, 33, 17, 29, 62, 64],
[38, 4, 8, 44, 86, 97, 82, 17, 94, 43, 27, 84, 40, 78, 26, 75, 93, 71, 48, 90, 83, 3, 17, 10, 37, 3, 34, 42,
11, 16, 3, 55, 5, 91, 77, 16, 4, 46, 77, 81, 86, 15, 38, 11, 47, 82, 68, 49, 19, 6],
[19, 66, 8, 99, 83, 51, 57, 39, 65, 53, 20, 75, 66, 48, 87, 54, 52, 81, 53, 58, 97, 20, 100, 96, 28, 53, 48,
78, 69, 43, 52, 39, 95, 56, 57, 55, 14, 44, 17, 8, 43, 29, 14, 8, 75, 96, 90, 47, 33, 92],
[78, 1, 7, 20, 35, 50, 99, 13, 33, 67, 32, 72, 53, 18, 61, 80, 18, 62, 15, 74, 36, 64, 19, 45, 25, 69, 62, 46,
19, 41, 43, 78, 79, 77, 76, 10, 82, 78, 57, 42, 32, 44, 87, 56, 21, 2, 8, 19, 52, 42],
[8, 7, 96, 17, 76, 83, 58, 64, 1, 79, 86, 75, 8, 53, 38, 86, 12, 84, 66, 27, 72, 77, 91, 16, 88, 39, 100, 22,
68, 1, 17, 68, 84, 12, 3, 50, 96, 4, 56, 12, 57, 32, 35, 47, 86, 96, 95, 57, 73, 2],
[9, 66, 43, 65, 14, 91, 58, 8, 14, 83, 24, 93, 4, 75, 38, 32, 3, 36, 19, 46, 65, 19, 75, 20, 85, 65, 21, 48,
26, 42, 33, 1, 21, 91, 11, 35, 3, 8, 45, 17, 56, 7, 14, 80, 100, 79, 90, 89, 97, 79],
[67, 92, 25, 26, 68, 76, 89, 60, 20, 32, 40, 21, 83, 47, 38, 55, 25, 94, 78, 9, 68, 29, 46, 35, 95, 11, 54, 57,
12, 7, 37, 48, 75, 22, 30, 36, 61, 45, 94, 58, 81, 99, 34, 4, 91, 90, 39, 21, 54, 73],
[24, 32, 74, 89, 91, 75, 59, 1, 74, 7, 47, 83, 42, 57, 93, 1, 74, 48, 60, 68, 4, 75, 71, 73, 49, 72, 62, 59,
90, 98, 81, 92, 12, 97, 95, 23, 17, 39, 12, 3, 64, 24, 34, 70, 76, 67, 16, 90, 11, 51],
[97, 52, 24, 40, 9, 79, 74, 84, 56, 58, 79, 87, 52, 61, 84, 93, 60, 22, 57, 62, 41, 37, 21, 38, 84, 50, 64, 11,
1, 44, 59, 44, 86, 62, 31, 39, 63, 48, 94, 89, 18, 35, 43, 70, 29, 21, 67, 35, 82, 10],
[5, 42, 78, 100, 30, 10, 13, 90, 60, 33, 93, 23, 83, 47, 89, 29, 79, 30, 92, 18, 56, 30, 9, 42, 28, 6, 87, 52,
94, 33, 15, 63, 97, 43, 35, 82, 59, 67, 96, 100, 12, 81, 15, 57, 26, 86, 27, 64, 31, 22],
[79, 82, 34, 62, 77, 51, 76, 3, 8, 7, 90, 91, 50, 62, 54, 87, 83, 92, 72, 37, 13, 6, 70, 81, 45, 95, 100, 95,
35, 46, 18, 2, 74, 31, 26, 18, 20, 45, 69, 62, 12, 28, 73, 10, 44, 36, 69, 95, 48, 7],
[99, 95, 48, 31, 5, 79, 2, 18, 79, 36, 72, 58, 45, 47, 26, 45, 34, 10, 11, 83, 40, 1, 27, 70, 77, 89, 11, 84,
33, 83, 57, 82, 48, 74, 48, 95, 73, 30, 26, 35, 78, 75, 33, 15, 80, 38, 3, 59, 80, 54],
[41, 33, 63, 14, 95, 54, 60, 32, 42, 83, 75, 61, 72, 10, 94, 38, 42, 29, 57, 37, 2, 47, 47, 55, 89, 76, 36, 39,
10, 15, 1, 50, 83, 94, 59, 39, 67, 59, 83, 58, 89, 15, 57, 77, 85, 30, 86, 13, 55, 92],
[39, 64, 98, 45, 15, 67, 90, 48, 28, 3, 7, 6, 38, 90, 6, 14, 82, 21, 19, 63, 31, 52, 90, 98, 56, 89, 98, 80, 6,
70, 3, 43, 69, 82, 45, 78, 58, 5, 23, 50, 82, 91, 27, 15, 87, 24, 10, 72, 11, 47],
[96, 56, 16, 87, 76, 48, 97, 29, 40, 78, 9, 72, 71, 23, 21, 27, 65, 36, 100, 49, 41, 99, 84, 35, 37, 82, 93,
43, 24, 83, 65, 39, 78, 10, 43, 36, 97, 79, 47, 43, 43, 90, 88, 34, 64, 83, 48, 83, 50, 7],
[62, 1, 80, 32, 87, 35, 38, 86, 86, 74, 2, 17, 51, 28, 31, 16, 46, 93, 60, 66, 70, 80, 30, 75, 53, 67, 67, 5,
8, 10, 5, 17, 71, 58, 26, 40, 31, 79, 95, 40, 26, 83, 74, 79, 40, 27, 37, 43, 61, 25],
[97, 52, 9, 23, 2, 8, 70, 13, 48, 24, 23, 26, 96, 71, 2, 48, 14, 93, 13, 32, 69, 91, 32, 7, 13, 71, 85, 26, 49,
74, 33, 35, 9, 13, 98, 83, 3, 43, 77, 10, 88, 39, 94, 69, 11, 29, 65, 20, 18, 40],
[16, 54, 97, 66, 62, 97, 66, 7, 66, 80, 42, 29, 57, 91, 78, 60, 100, 55, 39, 40, 95, 84, 44, 49, 93, 85, 35,
49, 10, 18, 7, 91, 76, 77, 58, 53, 4, 82, 95, 82, 77, 82, 64, 69, 5, 34, 37, 42, 26, 41],
[89, 35, 37, 77, 71, 98, 18, 42, 29, 50, 22, 85, 11, 41, 20, 42, 21, 42, 15, 80, 2, 37, 84, 50, 89, 59, 30, 91,
83, 40, 94, 7, 67, 66, 81, 65, 22, 42, 86, 68, 8, 30, 99, 94, 88, 3, 95, 52, 62, 28],
[29, 95, 24, 16, 9, 64, 45, 97, 54, 46, 56, 63, 17, 44, 74, 69, 11, 38, 43, 42, 13, 42, 77, 15, 62, 36, 84, 43,
9, 84, 100, 50, 73, 28, 24, 34, 9, 62, 13, 27, 7, 85, 20, 94, 100, 44, 18, 49, 13, 12],
[77, 67, 42, 49, 28, 62, 8, 66, 49, 10, 45, 10, 15, 6, 66, 43, 33, 3, 60, 28, 85, 73, 75, 19, 93, 100, 18, 70,
91, 66, 5, 48, 86, 79, 52, 32, 5, 41, 91, 17, 96, 39, 24, 92, 28, 54, 76, 50, 15, 36],
[79, 82, 74, 22, 68, 5, 62, 15, 54, 52, 77, 23, 52, 65, 10, 56, 5, 55, 49, 46, 26, 81, 33, 53, 97, 24, 3, 5,
75, 15, 15, 79, 97, 77, 93, 1, 72, 12, 91, 77, 77, 73, 87, 17, 46, 75, 52, 70, 36, 75],
[78, 7, 56, 28, 19, 97, 13, 80, 58, 97, 59, 77, 1, 5, 20, 72, 46, 62, 92, 57, 72, 99, 64, 45, 65, 41, 26, 62,
8, 39, 4, 3, 85, 7, 26, 53, 4, 2, 41, 29, 2, 23, 14, 25, 5, 10, 60, 49, 10, 64],
[18, 98, 23, 21, 32, 74, 66, 36, 75, 78, 27, 91, 74, 31, 51, 83, 13, 73, 8, 53, 58, 89, 7, 70, 21, 87, 56, 87,
23, 64, 72, 82, 61, 36, 91, 23, 50, 92, 38, 70, 68, 84, 74, 3, 70, 1, 62, 60, 25, 70],
[33, 45, 48, 40, 82, 37, 93, 92, 93, 23, 76, 93, 91, 55, 94, 63, 4, 48, 52, 4, 76, 96, 16, 16, 93, 40, 63, 100,
80, 56, 8, 56, 82, 96, 71, 34, 50, 10, 2, 39, 28, 90, 6, 2, 32, 6, 100, 15, 43, 63]]):
print(i)