如何找出数据中最小的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<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#中间处的坐标    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<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:#偶数
            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<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))

从三个有序的数组中找出他们的公共元素

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

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