Definition
已知一個(gè)2維矩陣，其中的元素每一行從左至右依次增加冰垄，每一列從上到下依次增加蹬癌。即對(duì)于矩陣Table有Table[i][j] ≤Table[i][j + 1], Table[i][j] ≤ Table[i + 1][j]，我們也稱這樣的矩陣為楊氏矩陣。
Insert
因?yàn)槊總€(gè)元素的下面一個(gè)元素和右面一個(gè)元素都會(huì)比當(dāng)前元素大逝薪，所以右下角的元素是最大的一個(gè)元素隅要。所以我們將元素放到矩陣的右下角，然后再來(lái)調(diào)整元素的位置董济。我們將這個(gè)元素與它上面的元素和左面的元素進(jìn)行比較步清，將最大的那個(gè)元素與這個(gè)元素進(jìn)行交換，如果這個(gè)元素就是最大的話虏肾，則已經(jīng)插入正確的位置廓啊。若上面和左面的兩個(gè)元素相等且大于這個(gè)元素，則我們可以交換哪一個(gè)都可以封豪。
Delete
我們要把矩陣中指定的一個(gè)元素去掉谴轮，那么我們需要調(diào)整它右面和下面的元素來(lái)符合楊氏矩陣的特性。所以我們不妨將要?jiǎng)h除的元素置為NAN吹埠。我們將這個(gè)元素與他右面和下面的元素中最小的那個(gè)進(jìn)行交換(類似insert操作)
Find
我們從右上角開始來(lái)查找第步，目的元素比當(dāng)前元素大則向下查，比當(dāng)前元素小則向左查缘琅。這樣們可以在2*n的次數(shù)內(nèi)找到想要的元素雌续。
Modify
我們將這個(gè)重新賦值的元素和它四周的元素進(jìn)行比較，通過交換調(diào)整位置來(lái)滿足楊氏矩陣的特性胯杭。
#-*-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]]