专栏首页一英里广度一英寸深度的学习三路快排算法-求中位数问题(4)

三路快排算法-求中位数问题(4)

算法面试高频题,求前K个数,或者求中位数

引至51CTO

三路快排算法思路

  1. 将数组分为三部分,随机选择数组中的一个数,使数组左边都小于这个数,右边大于这个数。
  2. 在递归处理左边数组,右边数组。

step1排列数组的时间复杂度是O(N),空间复杂度是O(1) step2 递归调用的复杂度O(logN)

总体的时间赋值度O(NlogN)

Step 1 算法解释

    def __QuickSort(self,a,l,r):
        #a[l,r)
        if(l+1>=r):
            return
        rand_index = random.randint(l,r-1) 
        self.swap(a,l,rand_index) ## 对已经排好序的数组,有优化作用
        gt = r ##右边的指针位置
        lt = l ##左边的指针位置
        i = l+1 ## 遍历指针
        while(i<gt): ##遍历条件
            if(a[i]>a[l]):
                self.swap(a,i,gt-1)
                gt = gt -1 ##将大数换到右端,大数指针--
            elif(a[i]<a[l]):
                self.swap(a,lt+1,i)
                i = i+1
                lt= lt+1 ## 将小数换到左端,小数指针--
            else:
                i = i+1 ## 相等的数据,步进指针++
        self.swap(a,l,lt) ##将小数的最后一个和第一个数交换,结果是[l,lt)是小数
        self.__QuickSort(a,gt,r)
        self.__QuickSort(a,l,lt) ##递归调用

求中位数算法

利用快速排序思想,只处理中位数所在的区域(中数、大数或小数)

  • 中位数在大数区,对大数区快速排序
  • 中位数在小数区,对小数区快速排序
  • 中位数在中数区,返回

考虑中位数是len//2,len//2-1情况

def __swap(a,i,j):
    tmp  = a[i]
    a[i] = a[j]
    a[j] = tmp
    
def insertSort(a,l,r):
    #a[l,r)
    i = l
    while(i<r):
        j = i
        while(j>l):
            if (a[j]<a[j-1]):
                __swap(a,j,j-1)                
            else:
                break 
            j = j-1
        i = i+1

def sortMid(a):
    mid = len(a)//2
    sortHead(a,mid)
    
def sortHead(a,k):
    #a[l,r)
    assert(k<len(a))
    __sortHead(a,0,len(a),k)

def __sortHead(a,l,r,k):
    if(r-l<10):
        insertSort(a,l,r)
        return    
    rand = random.randint(l,r-1)
    __swap(a,l,rand)
    
    lt = l
    gt = r
    i  = l
    while(i<gt):
        if(a[i]>a[l]):
            __swap(a,gt-1,i)
            gt = gt -1
        elif(a[i]<a[l]):
            __swap(a,lt+1,i)
            i= i +1
            lt = lt + 1
        else:
            i = i+1
    __swap(a,lt,l)
## 判断k在哪个区域
    if(k-1<lt):
        ## 将k-1也进行排序,考虑len//2-1
        __sortHead(a,l,lt,k)
    if(k>=gt):
        __sortHead(a,gt,r,k)

测试代码

import copy
for i in range(50):
    total = random.randint(0,200000)
    a = np.random.randint(0,total,500000)
    a.tolist()
    b =  copy.copy(a)
    a.sort()
    mid1 = a[len(a)//2]
    mid1_left = a[len(a)//2-1]
    sortMid(b)
    mid2 = b[len(a)//2]
    mid2_left = b[len(a)//2-1]
    if(mid1 == mid2 and mid1_left==mid2_left):
        print("True")
    else:
        print("Flase")

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Btrace学习笔记二

    curl http://localhost:8080/btrace/exception 运行结果打印19、20、22、25。

    birdskyws
  • MAT java 内存分析工具

    https://www.eclipse.org/mat/downloads.php

    birdskyws
  • Sqoop安装

    下载页面下有两个链接,使用sqoop-1.4.7.bin__hadoop-2.6.0.tar.gz,包含hadoop支持。不要用sqoop-1.4.7.tar....

    birdskyws
  • EventBus 源码解析

    PostThread:默认的 ThreadMode,表示在执行 Post 操作的线程直接调用订阅者的事件响应方法,不论该线程是否为主线程(UI 线程)。

    Yif
  • python3-泊松分布

    在实际事例中,当一个随机事件,例如某电话交换台收到的呼叫、来到某公共汽车站的乘客、某放射性物质发射出的粒子、显微镜下某区域中的白血球等等,以固定的平均瞬时速率...

    py3study
  • 如何在CentOS 7上的主代理安装程序中安装Puppet 4

    来自Puppet Labs的Puppet是一种配置管理工具,可帮助系统管理员自动化服务器基础架构的配置,配置和管理。提前规划并使用Puppet等配置管理工具可以...

    灬半痴
  • 【独家】中国无人驾驶新晋黑马:极客十年终创业,讯飞基金重磅天使

    【新智元导读】 根据新智元获得的独家消息,中国无人驾驶界又添一支重量级创业团队:拥有10多年研发经验的无人驾驶三极客创办“主线科技”,欲打造中国无人驾驶专用车第...

    新智元
  • 如何在Ubuntu 16.04上安装Puppet 4

    Puppet是一种配置管理工具,可帮助系统管理员自动化服务器基础架构的准备、配置和管理。提前规划并使用Puppet等配置管理工具可以减少重复基本任务所花费的时间...

    丰一川
  • 使用颜色空间进行图像分割

    原文地址:https://realpython.com/python-opencv-color-spaces/

    努力努力再努力F
  • C++核心准则C.21:默认操作要定义就全定义,要禁止就全禁止

    The special member functions are the default constructor, copy constructor, copy...

    面向对象思考

扫码关注云+社区

领取腾讯云代金券