如何用Python在无序数组中高效查找中位数？

本文共计1089个文字，预计阅读时间需要5分钟。

一、问题描述求一个无序数组的中间数。若数组是奇数，则中间数为中间两个数字之和除以2，减去2；若数组是偶数，则中间数为中间位置上的数字。

二、要求

1.不能使用排序。

2.时间复杂度尽可能低。

一、问题描述

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 ， 那么中位数点在右侧，反之，中位数在左侧。