python实现在无序数组中找到中位数方法-创新互联
一、问题描述
创新互联专业IDC数据服务器托管提供商,专业提供成都服务器托管,服务器租用,成都托管服务器,成都托管服务器,成都多线服务器托管等服务器托管服务。1、求一个无序数组的中位数, (若数组是偶数,则中位数是指中间两个数字之和除以2,若数组是奇数,则中位数是指最中间位置。要求:不能使用排序,时间复杂度尽量低
2、例如:
lists = [3, 2, 1, 4] , 中位数为 = (2+3)/2 = 2.5
lists = [3, 1, 2] , 中位数为 2
3、算法思想:
利用快速排序思想(但是并不是全部使用):任意挑选一个元素,以该元素为key, 划分数组为两个部分,如果左侧数组长度刚好为(n-1)/2, 那么key就为中位数, 若左侧数组长度 < (n-1)/2 , 那么中位数点在右侧,反之,中位数在左侧。然后进入相应的一侧继续寻找中位
平均时间复杂度为O(n)
二、程序
class Solution(object): def findmedian(self, lists): if not lists or len(lists) == 0: return [] n = len(lists) if n % 2 == 0: a = self.partition(lists, n/2, 0, n-1) b = self.partition(lists, n/2-1, 0, n-1) mid = (lists[a]+lists[b])/ (2 * 1.0) return mid else: mid = self.partition(lists, n/2, 0, n-1) return lists[mid] def partition(self, lists, k, start, end): key = lists[start] left, right = start, end while left < right: while left < right and lists[right] > key: right = right - 1 lists[left] = lists[right] while left < right and lists[left] < key: left = left + 1 lists[right] = lists[left] lists[left] = key if left == k: return left elif left > k: return self.partition(lists, k, start, left-1) else: return self.partition(lists, k, left+1, end) if __name__ == "__main__": sol = Solution() lists = [2, 5, 4, 9, 3, 6, 8, 7, 1] # lists = [1, 2] data = sol.findmedian(lists) print("中位数 = %s" % data)
另外有需要云服务器可以了解下创新互联scvps.cn,海内外云服务器15元起步,三天无理由+7*72小时售后在线,公司持有idc许可证,提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案,具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势,专为企业上云打造定制,能够满足用户丰富、多元化的应用场景需求。
网站栏目:python实现在无序数组中找到中位数方法-创新互联
本文来源:http://scyanting.com/article/dpeipj.html