数组，寻找第K大的数

思路解析（代码有问题）

1.最暴力的思想，直接排序，然后索引第k个数据，最优的排序算法时间复杂度为O(nlog(n)),但是随着n的变大，复杂度增长

2.借助快速排序的思想

　　快速排序的思想是通过一趟排序将要排序的list分为2部分，左边小，右边大。然后递归排序左右。我们可以在每一趟排序后，比较基准元素的索引和K的大小，若k大于基准元素的索引，则要寻找的k大数字就在基准元素的右边，否则左边。知道找到基准元素的索引等于K。

时间复杂度 O(n)

 def partition(data,left,right):

     if (len(data)<=0 or left<0 or right>=len(data)):

         print("Invalid parametres,please check!")
　　　　#基准元素为list的第一个元素　　

     temp = data[left]

     i = left

     j = right

     while (i != j):
           #两个指针，先动右边的指针，判断指针指向的元素是否小于基准元素，若小于，就要交换位置，移动到左边

         while (data[j]>=temp and i<j):

                 j = j-1

         while (data[i]<=temp and i<j):

                 i = i+1

         if (i<j):
               #data[i]与data[j]位置交换　　　　　

             t = data[i]

             data[j] = data[i]

             data[j] = t   
       #当i=j时，这时候list[i]=基准元素      data[i] = temp

     return i

 def find_k(data,k):

     n = len(data)

     left = 0

     right = n-1

     index = partition(data,left,right)

     while (index != k):

             if (index>k):

                 right = index-1

                 index = partition(data,left,right)

             else:

                 left = index+1

                 index = partition(data,left,right)

     return data[k]

 if __name__ == "__main__":

         data = [6,9,2,4,5,7,9,3,4]

         a = 2

         k = len(data) -a

         result = find_k(data,k)

         print(result)

巴特西

数组，寻找第K大的数

最新文章

热门文章