如何找出數(shù)據(jù)中最小的k個(gè)數(shù)
方法一：將數(shù)據(jù)排序，然后從排好序的數(shù)組中找到第k小的數(shù)
方法二：使用選擇排序的方式，排序k次，找到第k小的數(shù)
方法三：使用快速排序的思想，從中隨機(jī)選擇一個(gè)數(shù)mid，然后將其劃分為三部分
array[low.mid-1]、array[mid]、array[mid+1,high]，也就是這三個(gè)部分，如果mid-low=k-1那么我們認(rèn)為array[mid]就是我們所需要找到的，如果mid-low>k-1,那么我們需要從[low,mid-1]中找到第k小的數(shù)。如果mid-low<k-1那么我們需要從array[mid+1，high]中找到最小的第k-(mid-low)-1小的值就可以了。
def findsmallK(array,low,high,k): i=low j=high middata=array[i] while i<j:
while i<j and array[j]>=middata:
j-=1
if i<j:
array[i]=array[j] i+=1
while i<j and array[i]<=middata:
i+=1
if i<j:
array[j]=array[i] j-=1
array[i]=middata#i就是中間值 subArrayIndex=i-low#中間處的坐標(biāo) if subArrayIndex==k-1:
return array[i]
elif subArrayIndex>k-1:
return findsmallK(array,low,i-1,k)
else :
return findsmallK(array,i+1,high,k-(i-low)-1)
if __name__=="__main__":
array=[4,0,1,0,2,3]
k=6
data=findsmallK(array,0,len(array)-1,k)
print(data)
如何求數(shù)組連續(xù)最大和
我們可以維護(hù)兩個(gè)空間，一個(gè)空間用于計(jì)算每個(gè)能夠連續(xù)的最大和，而另外一個(gè)用于存儲(chǔ)最大的和
def arrsum(arr): arrlength=len(arr)
S=[None]*arrlength#記錄連續(xù)的計(jì)算和 MS=[None]*arrlength#記錄最大的和 S[0]=arr[0]
MS[0]=arr[0]
i=1
while i<arrlength:
S[i]=max(S[i-1]+arr[i],arr[i])
MS[i]=max(MS[i-1],S[i])
i+=1
return MS[arrlength-1]
if __name__=="__main__":
arr=[1,-2,4,8,-4,7,-1,-5]
data=sum=arrsum(arr) print(data)
還可以不維護(hù)空間，而是直接計(jì)算最大值：
def arrsum(arr): arrlength=len(arr)
#S=[None]*arrlength#記錄連續(xù)的計(jì)算和 #MS=[None]*arrlength#記錄最大的和 #S[0]=arr[0]
#MS[0]=arr[0]
S=arr[0]
MS=arr[0]
i=1
while i<arrlength:
S=max(S+arr[i],arr[i])
MS=max(MS,S)
i+=1
return MS
if __name__=="__main__":
arr=[1,2,3,-4]
data=sum=arrsum(arr) print(data)
計(jì)算最大子組的位置
計(jì)算最大子組和最大子組的位置，關(guān)鍵在于只要目前nMax相加的是負(fù)數(shù)，那么說(shuō)明前面的已經(jīng)沒(méi)有意義了,那么就需要重新統(tǒng)計(jì)，如果要是為正，那么加上一切可以加上的，如果加上的比Smax要大，那么說(shuō)明這個(gè)有意義，我們需要更改一些信息（這里永遠(yuǎn)記錄最有用的信息），但是如果加上還沒(méi)有那個(gè)大，那說(shuō)明加上的沒(méi)有意義。
class Demo:
def __init__(self):
self.begin=0
self.end=0
def maxArrayValue(self,arr):
nMax=-2**31
SMax=0
st=0
i=0
lengths=len(arr) while i<lengths:
if nMax<0:#只要小于0，那么就永遠(yuǎn)接收最新的
nMax=arr[i] st=i else:
nMax=nMax+arr[i] if nMax>SMax:
self.begin=st
self.end=i
SMax=nMax i+=1
return SMax
def getBegin(self):
return self.begin
def getEnd(self):
return self.end
if __name__=="__main__":
arr=[1,-2,4,8,-4,7,-1,-5]
d=Demo() data=d.maxArrayValue(arr) print(data) print(d.begin,d.end)
如何求數(shù)組中兩個(gè)元素的最小距離
def minDistance(array,num1,num2):
if array==None or len(array)<1:
return None
lastnumindex1=-1
lastnumindex2=-1
i=0
mindis=2**30
while i<len(array):
if array[i]==num1:
lastnumindex1=i
if lastnumindex2>0:
mindis=min(mindis,abs(lastnumindex2-lastnumindex1))
if array[i]==num2:
lastnumindex2=i
if lastnumindex1>0:
mindis=min(mindis,abs(lastnumindex2-lastnumindex1))
i+=1
return mindis
if __name__=="__main__":
arr = [4, 6, 7, 4, 7, 4, 6, 4, 7, 8, 5, 6, 4, 3, 10, 8]
num1 = 4
num2 = 8
print(minDistance(arr,num1,num2))
求三元組的距離
def MinDistance(a,b,c):
minDist=2**23
i=0
j=0
k=0
d=0
while True:
d=max(abs(a[i]-b[j]),abs(a[i]-c[k]))
d=max(d,abs(c[k]-b[j]))
if d<minDist:
minDist=d m1=min(a[i],b[j])
m2=min(m1,c[k])
if m2==a[i]:
#print(a[i])
i+=1
if i>len(a)-1:
print(a[i-1],b[j],c[k])
break
elif m2==b[j]: j+=1
if j>len(b)-1:
break
else:
k += 1
if k > len(c) - 1:
break
return minDist
if __name__=="__main__":
a = [3, 4, 5, 7, 15]
b = [10, 12, 14, 16, 17]
c = [20, 21, 23, 24, 30, 37]
dis=MinDistance(a,b,c)
print(dis)
如何在不排序的情況下求中位數(shù)
def findMid(array,low,high,k): i=low#獲取起始的坐標(biāo) j=high#獲取終止的坐標(biāo) firstdata = array[i] # 獲取中間元素 while i<j:
while i<j and array[j]>=firstdata:
j-=1
if i<j:
array[i]=array[j] i+=1
while i<j and array[i]<=firstdata:
i+=1
if i<j:
array[j]=array[i] j-=1
array[i]=firstdata if i-low==k-1:
if len(array)%2 == 0:#偶數(shù)
return (array[i]+array[i+1])/2
else:
return array[i]
elif i-low>k-1:
return findMid(array,low,i-1,k)
else:
return findMid(array,i+1,high,k-(i-low)-1)
if __name__=="__main__":
array=[1,2,3,4,5]
low=0
high=len(array)-1
if len(array)%2==0:
k=(len(array))//2
else:
k=(len(array))//2+1
#k表示第幾小 data=findMid(array,low,high,k) print(data)
如何獲取最好的矩陣鏈相乘方法
def MatrixChainOrder(array,i,j):
if i==j:
return 0
mins=2**32
k=i while k<j:
min=MatrixChainOrder(array,i,k)+MatrixChainOrder(array,k+1,j)+array[i-1]*array[k]*array[j]
if min<mins:
mins=min k+=1
return mins
if __name__=="__main__":
array=[1,5,2,4,6]
print(MatrixChainOrder(array,1,len(array)-1))#將除了第一個(gè)和最后一個(gè)的包裹起來(lái)
如何對(duì)大量重復(fù)的數(shù)字進(jìn)行排序
def sort(array):
data_count=dict() i=0
while i<len(array):
if str(array[i]) in data_count:
data_count[str(array[i])]=data_count.get(str(array[i]))+1
else:
data_count[str(array[i])]=1
i+=1
index=0
#print(data_count)
for key in sorted(data_count.keys(),key=lambda d:int(d)):
i=data_count[key] while i>0:
array[index]=key index+=1
i-=1
if __name__=="__main__":
array=[15,12,15,2,2,12,2,3,12,100,3,3]
sort(array)
i=0
while i<len(array):
print(array[i])
i+=1
如何在有規(guī)律的二維數(shù)組中進(jìn)行高效的數(shù)據(jù)查找
def findWithBinary(array,data): if array==None or len(array)<1:
print("參數(shù)不合理")
return False
i=0
rows=len(array)
columns=len(array[0])
j=columns-1
while i<rows and j>=0:
if array[i][j]==data:
return True elif array[i][j]>data:
j-=1 else: i+=1 return Falseif __name__=="__main__":
array=[[1,2,3,4],[11,12,13,14],[21,22,23,24],[31,32,33,34],[41,42,43,44]] print(findWithBinary(array,17)) print(findWithBinary(array,24))
從三個(gè)有序的數(shù)組中找出他們的公共元素
def findCommon(array1,array2,array3):
i=0
j=0
k=0
while i<len(array1) and j<len(array2)and k<len(array3):
if array1[i]==array2[j]==array3[k]:
i+=1
j+=1
k+=1
print(array1[i-1])
elif array1[i]<array2[j]:
i+=1
elif array2[j]<array3[k]:
j+=1
else:
k+=1
if __name__=="__main__":
array1=[2,5,12,20,45,85]
array2=[16,19,20,85,200]
array3=[3,4,15,20,39,72,85,190]
findCommon(array1,array2,array3)
如何求一個(gè)字符串所有的排列
def swap(str,index1,index2):
tmp=str[index1]
str[index1]=str[index2]
str[index2]=tmp
#看成是兩個(gè)子問(wèn)題，一個(gè)子問(wèn)題的從一個(gè)字符縮減角度，另外一個(gè)是從替換的角度def Permutation(str,start):
if str is None and start <0:
return
if start==len(str)-1:
print("".join(str))
else:
i = start while i<len(str):
swap(str,start,i)
Permutation(str,start+1)
swap(str,start,i)
i+=1
def Permutation_transe(s): str=list(s)
Permutation(str,0)
if __name__=="__main__":
a="abc"
Permutation_transe(a) print()
遞歸問(wèn)題的核心是將問(wèn)題轉(zhuǎn)變?yōu)樽訂?wèn)題，然后還要設(shè)置好結(jié)束條件
