江苏龙网

  1. 主页 > 生活百科 > >

python语言实现 十道经典的算法编程题目

算法

如何找出数据中最小的k个数方法一：将数据排序，然后从排好序的数组中找到第k小的数
方法二：使用选择排序的方式，排序k次，找到第k小的数
方法三：使用快速排序的思想，从中随机选择一个数mid，然后将其划分为三部分
array[low.mid-1]、array[mid]、array[mid+1,high]，也就是这三个部分，如果mid-low=k-1那么我们认为array[mid]就是我们所需要找到的，如果mid-low>k-1,那么我们需要从[low,mid-1]中找到第k小的数 。如果mid-low<k-1那么我们需要从array[mid+1，high]中找到最小的第k-(mid-low)-1小的值就可以了 。
def findsmallK(array,low,high,k):i=lowj=highmiddata=array[i]while i<j:while i<j and array[j]>=middata:j-=1if i<j:array[i]=array[j]i+=1while i<j and array[i]<=middata:i+=1if i<j:array[j]=array[i]j-=1array[i]=middata#i就是中间值subArrayIndex=i-low#中间处的坐标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=6data=findsmallK(array,0,len(array)-1,k)print(data)如何求数组连续最大和我们可以维护两个空间，一个空间用于计算每个能够连续的最大和，而另外一个用于存储最大的和
def arrsum(arr):arrlength=len(arr)S=[None]*arrlength#记录连续的计算和MS=[None]*arrlength#记录最大的和S[0]=arr[0]MS[0]=arr[0]i=1while i<arrlength:S[i]=max(S[i-1]+arr[i],arr[i])MS[i]=max(MS[i-1],S[i])i+=1return MS[arrlength-1]if __name__=="__main__":arr=[1,-2,4,8,-4,7,-1,-5]data=https://www.isolves.com/it/cxkf/yy/Python/2020-09-30/sum=arrsum(arr)print(data)还可以不维护空间，而是直接计算最大值：
def arrsum(arr):arrlength=len(arr)#S=[None]*arrlength#记录连续的计算和#MS=[None]*arrlength#记录最大的和#S[0]=arr[0]#MS[0]=arr[0]S=arr[0]MS=arr[0]i=1while i<arrlength:S=max(S+arr[i],arr[i])MS=max(MS,S)i+=1return MSif __name__=="__main__":arr=[1,2,3,-4]data=https://www.isolves.com/it/cxkf/yy/Python/2020-09-30/sum=arrsum(arr)print(data)计算最大子组的位置计算最大子组和最大子组的位置，关键在于只要目前nMax相加的是负数，那么说明前面的已经没有意义了,那么就需要重新统计，如果要是为正，那么加上一切可以加上的，如果加上的比Smax要大，那么说明这个有意义，我们需要更改一些信息（这里永远记录最有用的信息），但是如果加上还没有那个大，那说明加上的没有意义 。
class Demo:def __init__(self):self.begin=0self.end=0def maxArrayValue(self,arr):nMax=-2**31SMax=0st=0i=0lengths=len(arr)while i<lengths:if nMax<0:#只要小于0，那么就永远接收最新的nMax=arr[i]st=ielse:nMax=nMax+arr[i]if nMax>SMax:self.begin=stself.end=iSMax=nMaxi+=1return SMaxdef getBegin(self):return self.begindef getEnd(self):return self.endif __name__=="__main__":arr=[1,-2,4,8,-4,7,-1,-5]d=Demo()data=https://www.isolves.com/it/cxkf/yy/Python/2020-09-30/d.maxArrayValue(arr)print(data)print(d.begin,d.end)如何求数组中两个元素的最小距离def minDistance(array,num1,num2):if array==None or len(array)<1:return Nonelastnumindex1=-1lastnumindex2=-1i=0mindis=2**30while i<len(array):if array[i]==num1:lastnumindex1=iif lastnumindex2>0:mindis=min(mindis,abs(lastnumindex2-lastnumindex1))if array[i]==num2:lastnumindex2=iif lastnumindex1>0:mindis=min(mindis,abs(lastnumindex2-lastnumindex1))i+=1return mindisif __name__=="__main__":arr = [4, 6, 7, 4, 7, 4, 6, 4, 7, 8, 5, 6, 4, 3, 10, 8]num1 = 4num2 = 8print(minDistance(arr,num1,num2))求三元组的距离def MinDistance(a,b,c):minDist=2**23i=0j=0k=0d=0while 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=dm1=min(a[i],b[j])m2=min(m1,c[k])if m2==a[i]:#print(a[i])i+=1if i>len(a)-1:print(a[i-1],b[j],c[k])breakelif m2==b[j]:j+=1if j>len(b)-1:breakelse:k += 1if k > len(c) - 1:breakreturnminDistif __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)如何在不排序的情况下求中位数def findMid(array,low,high,k):i=low#获取起始的坐标j=high#获取终止的坐标firstdata = array[i]# 获取中间元素while i<j:while i<j and array[j]>=firstdata:j-=1if i<j:array[i]=array[j]i+=1while i<j and array[i]<=firstdata:i+=1if i<j:array[j]=array[i]j-=1array[i]=firstdataif i-low==k-1:if len(array)%2 == 0:#偶数return (array[i]+array[i+1])/2else: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=0high=len(array)-1if len(array)%2==0:k=(len(array))//2else:k=(len(array))//2+1#k表示第几小data=findMid(array,low,high,k)print(data)


推荐阅读


上一篇：使用布隆过滤器用于Python网络爬虫URL去重

下一篇：家中无线网信号差的解决方法之路由器的有/无线桥接。