Definition
已知一个2维矩阵，其中的元素每一行从左至右依次增加，每一列从上到下依次增加。即对于矩阵Table有Table[i][j] ≤Table[i][j + 1], Table[i][j] ≤ Table[i + 1][j]，我们也称这样的矩阵为杨氏矩阵。
Insert
因为每个元素的下面一个元素和右面一个元素都会比当前元素大，所以右下角的元素是最大的一个元素。所以我们将元素放到矩阵的右下角，然后再来调整元素的位置。我们将这个元素与它上面的元素和左面的元素进行比较，将最大的那个元素与这个元素进行交换，如果这个元素就是最大的话，则已经插入正确的位置。若上面和左面的两个元素相等且大于这个元素，则我们可以交换哪一个都可以。
Delete
我们要把矩阵中指定的一个元素去掉，那么我们需要调整它右面和下面的元素来符合杨氏矩阵的特性。所以我们不妨将要删除的元素置为NAN。我们将这个元素与他右面和下面的元素中最小的那个进行交换(类似insert操作)
Find
我们从右上角开始来查找，目的元素比当前元素大则向下查，比当前元素小则向左查。这样们可以在2*n的次数内找到想要的元素。
Modify
我们将这个重新赋值的元素和它四周的元素进行比较，通过交换调整位置来满足杨氏矩阵的特性。
#-*-coding:utf-8-*-
from numpy import *
def insert(m, value, i, j):
m[i][j] = value
largesti = i
largestj = j
if i-1>=0 and (isnan(m[i-1][j]) or m[i-1][j] > m[i][j]):
largesti = i-1
largestj = j
if j-1>=0 and (isnan(m[i][j-1]) or m[i][j-1] > m[largesti][largestj]):
largesti = i
largestj = j - 1
if i!=largesti or j!=largestj:
temp = m[i][j]
m[i][j] = m[largesti][largestj]
m[largesti][largestj] = m[i][j]
insert(m,value,largesti,largestj)
def delete(m, i, j):
m[i][j] = NAN
mini = i
minj = j
if i+1<m.shape[0]:
mini = i+1
minj = j
if j+1<m.shape[1] and (isnan(m[mini][minj]) or m[i][j+1] < m[mini][minj]):
mini = i
minj = j+1
if mini!=i or minj!=j:
temp = m[i][j]
m[i][j] = m[mini][minj]
m[mini][minj] = temp
delete(m, mini, minj)
def find(m,value):
i = 0
j = m.shape[1] - 1
while i<m.shape[0] and j >=0:
if isnan(m[i][j]) or m[i][j] > value:
j = j -1
elif isnan(value) or m[i][j] < value:
i = i+ 1
else:
return True
return False
def modify(m, i, j, value):
m[i][j] = value
nexti = i
nextj = j
if i-1>=0 and m[i-1][j] > m[i][j]:
nexti = i-1
nextj = j
if j-1>=0 and m[i][j-1] > m[nexti][nextj]:
nexti = i
nextj = j-1
if i+1<m.shape[0] and m[i][j] > m[i+1][j]:
nexti = i+1
nextj = j
if j+1<m.shape[1] and( isnan(m[nexti][nextj]) or m[i][j+1] < m[nexti][nextj]):
nexti = i
nextj = j+1
if nexti!=i or nextj!=j:
temp = m[i][j]
m[i][j] = m[nexti][nextj]
m[nexti][nextj] = temp
modify(m, nexti, nextj, value)
if __name__ == '__main__':
m = array([[2,4,6,NAN],[3,7,10,NAN],[5,12,NAN,NAN],[8,NAN,NAN,NAN]])
h,v = m.shape
print 'matrix'
print m
print '-'*24
print 'after insert 7'
insert(m,7,h-1,v-1)
print m
print '-'*24
print 'after delete m[0][0]'
delete(m,0,0)
print m
print '-'*24
print 'if 12 in the matrix'
print find(m,12)
print '-'*24
print 'after update m[1][1] to 1'
modify(m, 1, 1,1)
print m
脚本输出
matrix
[[ 2. 4. 6. nan]
[ 3. 7. 10. nan]
[ 5. 12. nan nan]
[ 8. nan nan nan]]
------------------------
after insert 7
[[ 2. 4. 6. nan]
[ 3. 7. 10. nan]
[ 5. 7. nan nan]
[ 8. 12. nan nan]]
------------------------
after delete m[0][0]
[[ 3. 4. 6. nan]
[ 5. 7. 10. nan]
[ 7. 12. nan nan]
[ 8. nan nan nan]]
------------------------
if 12 in the matrix
True
------------------------
after update m[1][1] to 1
[[ 1. 4. 6. nan]
[ 3. 5. 10. nan]
[ 7. 12. nan nan]
[ 8. nan nan nan]]
网友评论