数组的中位数)
给定一个数组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)
基本思路是对数组进行排序，并检查数组大小，如果数组大小为奇数则返回中间元素，否则返回中间两个元素的平均值。
using System;
using System.Linq;
class GfG {
static double FindMedian(int[] arr) {
int n = arr.Length;
// First we sort the array
Array.Sort(arr);
// check for even case
if (n % 2 != 0)
return arr[n / 2];
return (arr[(n - 1) / 2] + arr[n / 2]) / 2.0;
}
static void Main() {
int[] arr = { 1, 3, 4, 2, 7, 5, 8, 6 };
double ans = FindMedian(arr);
Console.WriteLine(ans);
}
}
输出
4.5
时间复杂度：O(n log n)，因为我们需要先对数组进行排序。
辅助空间：O(1)
【预期方法】：使用随机快速选择
要找到数组的中位数，可以随机选择一个基准元素，然后使用快速排序算法对数组进行分区，将较小的元素放在左侧，较大的元素放在右侧。如果基准元素落在中间索引处，则该元素即为中位数。否则，递归地对相应的子数组应用此过程。对于偶数大小的数组，可以找到中间两个元素并计算它们的平均值。
using System;
using System.Linq;
class GfG {
static void Swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
public static int Partition(int[] arr, int l, int r) {
int lst = arr[r], i = l, j = l;
while (j < r) {
if (arr[j] < lst) {
Swap(arr, i, j);
i++;
}
j++;
}
Swap(arr, i, r);
return i;
}
public static int RandomPartition(int[] arr, int l, int r) {
Random rand = new Random();
int n = r - l + 1;
int pivot = rand.Next(n);
Swap(arr, l + pivot, r);
return Partition(arr, l, r);
}
public static void MedianUtil(int[] arr, int l, int r, int k, int[] a, int[] b) {
if (l <= r) {
int 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;
} else if (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);
}
}
public static double FindMedian(int[] arr) {
double ans;
int[] a = {-1};
int[] b = {-1};
int n = arr.Length;
if (n % 2 == 1) {
MedianUtil(arr, 0, n - 1, n / 2, a, b);
ans = b[0];
} else {
MedianUtil(arr, 0, n - 1, n / 2, a, b);
ans = (a[0] + b[0]) / 2.0;
}
return ans;
}
public static void Main(string[] args) {
int[] arr = {12, 3, 6, 7, 4, 19};
Console.WriteLine(FindMedian(arr));
}
}
输出
6.5
时间复杂度：
- 最佳情况分析：O(1)
- 平均情况分析：O(n)
- 最坏情况分析：O(n 2 )
辅助空间：O(n)
【最坏情况线性时间方法】——使用顺序统计量
这种新方法的思路与 quickSelect() 类似。我们通过选择一个能够平衡分割数组的枢轴点（避免一侧元素极少而另一侧元素过多），来实现最坏情况下的线性时间复杂度。数组被平衡分割后，我们采用与 quickSelect() 相同的步骤来决定从枢轴点的左侧还是右侧进行选择。有关实现细节和更多详情，请参阅“无序数组中第 K 个最小/最大元素 | 最坏情况下的线性时间复杂度” 。
注意：虽然这种方法在理论上看起来不错，但之前的快速选择方法在实践中效果更好。
如果您喜欢此文章，请收藏、点赞、评论，谢谢，祝您快乐每一天。
