我要评论给定一个数组arr[]，任务是找到该数组的中位数。大小为 n 的数组的中位数定义为：当 n 为奇数时，中位数为中间元素；当 n 为偶数时，中位数为中间两个元素的平均值。
例如：
输入： arr[] = [12, 3, 5, 7, 4, 19, 26]
输出： 7
说明：给定数组 arr[] = [3, 4, 5, 7, 12, 19, 26] 的排序序列。由于元素个数为奇数，因此中位数是给定数组 arr[] 排序序列中的第 4 个元素，即 7。
输入： arr[] = [12, 3, 5, 7, 4, 26]
输出： 6
说明：由于元素个数为偶数，中位数是给定数组 arr[] 排序后的第 3 个元素和第 4 个元素的平均值，即 (5 + 7)/2 = 6
【朴素方法】通过对数组进行排序——时间复杂度为 o(n log n)，空间复杂度为 o(1)
基本思路是对数组进行排序，并检查数组大小，如果数组大小为奇数则返回中间元素，否则返回中间两个元素的平均值。
def findmedian(arr):
n = len(arr)
# first we sort the array
arr.sort()
# check for even case
if n % 2 != 0:
return arr[n // 2]
return (arr[(n - 1) // 2] + arr[n // 2]) / 2.0
if __name__ == "__main__":
arr = [1, 3, 4, 2, 7, 5, 8, 6]
ans = findmedian(arr)
print(ans)输出
4.5
时间复杂度： o(n log n)，因为我们需要先对数组进行排序。
辅助空间： o(1)
【预期方法】：使用随机快速选择
要找到数组的中位数，可以随机选择一个基准元素，然后使用快速排序算法对数组进行分区，将较小的元素放在左侧，较大的元素放在右侧。如果基准元素落在中间索引处，则该元素即为中位数。否则，递归地对相应的子数组应用此过程。对于偶数大小的数组，可以找到中间两个元素并计算它们的平均值。
import random
def swap(arr, i, j):
arr[i], arr[j] = arr[j], arr[i]
def partition(arr, l, r):
lst = arr[r]
i = l
j = l
while j < r:
if arr[j] < lst:
swap(arr, i, j)
i += 1
j += 1
swap(arr, i, r)
return i
def randompartition(arr, l, r):
n = r - l + 1
pivot = random.randint(0, n - 1)
swap(arr, l + pivot, r)
return partition(arr, l, r)
def medianutil(arr, l, r, k, a, b):
if l <= r:
partitionindex = randompartition(arr, l, r)
# find the median of odd number element in arr[]
if partitionindex == k:
b[0] = arr[partitionindex]
if a[0] != -1:
return
elif partitionindex == k - 1: # a & b as middle element of arr[]
a[0] = arr[partitionindex]
if b[0] != -1:
return
# index in first half of the arr[]
if partitionindex >= k:
medianutil(arr, l, partitionindex - 1, k, a, b)
# find the index in second half of the arr[]
else:
medianutil(arr, partitionindex + 1, r, k, a, b)
def findmedian(arr):
a = [-1]
b = [-1]
n = len(arr)
if n % 2 == 1:
medianutil(arr, 0, n - 1, n // 2, a, b)
return b[0]
else:
medianutil(arr, 0, n - 1, n // 2, a, b)
return (a[0] + b[0]) / 2.0
if __name__ == '__main__':
arr = [12, 3, 6, 7, 4, 19]
print(findmedian(arr))输出
6.5
时间复杂度：
- 最佳情况分析：o(1)
- 平均情况分析：o(n)
- 最坏情况分析：o(n 2 )
辅助空间： o(n)
【最坏情况线性时间方法】——使用顺序统计量
这种新方法的思路与 quickselect() 类似。我们通过选择一个能够平衡分割数组的枢轴点（避免一侧元素极少而另一侧元素过多），来实现最坏情况下的线性时间复杂度。数组被平衡分割后，我们采用与 quickselect() 相同的步骤来决定从枢轴点的左侧还是右侧进行选择。有关实现细节和更多详情，请参阅“无序数组中第 k 个最小/最大元素 | 最坏情况下的线性时间复杂度” 。
注意：虽然这种方法在理论上看起来不错，但之前的快速选择方法在实践中效果更好。
总结
到此这篇关于python数组中位数的文章就介绍到这了,更多相关python数组的中位数内容请搜索代码网以前的文章或继续浏览下面的相关文章希望大家以后多多支持代码网！
发表评论