C# (Median of an Array)数组的中位数

给定一个数组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 arrayArray.Sort(arr);// check for even caseif (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[]elseMedianUtil(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 个最小/最大元素 | 最坏情况下的线性时间复杂度” 。注意虽然这种方法在理论上看起来不错但之前的快速选择方法在实践中效果更好。如果您喜欢此文章请收藏、点赞、评论谢谢祝您快乐每一天。