如何找出数据中最小的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=low

　　j=high

　　middata=array[i]

　　while i<j:

　　while i=middata:

　　j-=1

　　if i<j:

　　array[i]=array[j]

　　i+=1

　　while i

　　i+=1

　　if i<j:

　　array[j]=array[i]

　　j-=1

　　array[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=6

　　data=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=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)

　　还可以不维护空间，而是直接计算最大值：

　　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=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)计算最大子组的位置

　　计算最大子组和最大子组的位置，关键在于只要目前nMax相加的是负数，那么说明前面的已经没有意义了,那么就需要重新统计，如果要是为正，那么加上一切可以加上的，如果加上的比Smax要大，那么说明这个有意义，我们需要更改一些信息（这里永远记录最有用的信息），但是如果加上还没有那个大，那说明加上的没有意义。

　　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，那么就永远接收最新的

　　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)

　　如何求数组中两个元素的最小距离

　　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)

　　如何在不排序的情况下求中位数

　　def findMid(array,low,high,k):

　　i=low#获取起始的坐标

　　j=high#获取终止的坐标

　　firstdata=array[i] # 获取中间元素

　　while i<j:

　　while i=firstdata:

　　j-=1

　　if i<j:

　　array[i]=array[j]

　　i+=1

　　while i

　　i+=1

　　if i<j:

　　array[j]=array[i]

　　j-=1

　　array[i]=firstdata

　　if i-low==k-1:

　　if len(array)%2==0:#偶数

　　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))#将除了第一个和最后一个的包裹起来如何对大量重复的数字进行排序

　　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如何在有规律的二维数组中进行高效的数据查找

　　def findWithBinary(array,data):

　　if array==None or len(array)<1:

　　print("参数不合理")

　　return False

　　i=0

　　rows=len(array)

　　columns=len(array[0])

　　j=columns-1

　　while i=0:

　　if array[i][j]==data:

　　return True

　　elif array[i][j]>data:

　　j-=1

　　else:

　　i+=1

　　return False

　　if __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))从三个有序的数组中找出他们的公共元素

　　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)如何求一个字符串所有的排列

　　def swap(str,index1,index2):

　　tmp=str[index1]

　　str[index1]=str[index2]

　　str[index2]=tmp

　　#看成是两个子问题，一个子问题的从一个字符缩减角度，另外一个是从替换的角度

　　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()

　　递归问题的核心是将问题转变为子问题，然后还要设置好结束条件