小数の配列を受け入れる関数を作成する必要があり、中央値を見つけます。
.net Math ライブラリに関数はありますか?
Rafe に感謝します。これは、返信者が投稿した問題を考慮したものです。
public static double GetMedian(double[] sourceNumbers) {
//Framework 2.0 version of this method. there is an easier way in F4
if (sourceNumbers == null || sourceNumbers.Length == 0)
throw new System.Exception("Median of empty array not defined.");
//make sure the list is sorted, but use a new array
double[] sortedPNumbers = (double[])sourceNumbers.Clone();
Array.Sort(sortedPNumbers);
//get the median
int size = sortedPNumbers.Length;
int mid = size / 2;
double median = (size % 2 != 0) ? (double)sortedPNumbers[mid] : ((double)sortedPNumbers[mid] + (double)sortedPNumbers[mid - 1]) / 2;
return median;
}
decimal Median(decimal[] xs) {
Array.Sort(xs);
return xs[xs.Length / 2];
}
トリックを行う必要があります。
- 編集 -
完全なモンティが必要な場合は、完全で短い純粋なソリューションを次に示します (空でない入力配列が想定されます)。
decimal Median(decimal[] xs) {
var ys = xs.OrderBy(x => x).ToList();
double mid = (ys.Count - 1) / 2.0;
return (ys[(int)(mid)] + ys[(int)(mid + 0.5)]) / 2;
}
.net Math ライブラリに関数はありますか?
いいえ。
とはいえ、自分で書くのは難しくありません。素朴なアルゴリズムは配列をソートし、中央 (または中央の 2 つの要素の平均) の要素を選択します。ただし、このアルゴリズムは、O(n log n)
この問題をO(n)
時間内に解決することができます。そのようなアルゴリズムを取得するには、選択アルゴリズムを調べます。
ジェイソンの答えの一般的なバージョンは次のとおりです
/// <summary>
/// Gets the median value from an array
/// </summary>
/// <typeparam name="T">The array type</typeparam>
/// <param name="sourceArray">The source array</param>
/// <param name="cloneArray">If it doesn't matter if the source array is sorted, you can pass false to improve performance</param>
/// <returns></returns>
public static T GetMedian<T>(T[] sourceArray, bool cloneArray = true) where T : IComparable<T>
{
//Framework 2.0 version of this method. there is an easier way in F4
if (sourceArray == null || sourceArray.Length == 0)
throw new ArgumentException("Median of empty array not defined.");
//make sure the list is sorted, but use a new array
T[] sortedArray = cloneArray ? (T[])sourceArray.Clone() : sourceArray;
Array.Sort(sortedArray);
//get the median
int size = sortedArray.Length;
int mid = size / 2;
if (size % 2 != 0)
return sortedArray[mid];
dynamic value1 = sortedArray[mid];
dynamic value2 = sortedArray[mid - 1];
return (sortedArray[mid] + value2) * 0.5;
}
これはQuickSelectの実装です。これは、この記事から引用したunsafe
C コードの実装であり、いくつかのアルゴリズムを比較し、QuickSelect が平均して最速であることがわかります。
[MethodImpl(MethodImplOptions.AggressiveInlining)]
private static unsafe void SwapElements(int* p, int* q)
{
int temp = *p;
*p = *q;
*q = temp;
}
public static unsafe int Median(int[] arr, int n)
{
int middle, ll, hh;
int low = 0; int high = n - 1; int median = (low + high) / 2;
fixed (int* arrptr = arr)
{
for (;;)
{
if (high <= low)
return arr[median];
if (high == low + 1)
{
if (arr[low] > arr[high])
SwapElements(arrptr + low, arrptr + high);
return arr[median];
}
middle = (low + high) / 2;
if (arr[middle] > arr[high])
SwapElements(arrptr + middle, arrptr + high);
if (arr[low] > arr[high])
SwapElements(arrptr + low, arrptr + high);
if (arr[middle] > arr[low])
SwapElements(arrptr + middle, arrptr + low);
SwapElements(arrptr + middle, arrptr + low + 1);
ll = low + 1;
hh = high;
for (;;)
{
do ll++; while (arr[low] > arr[ll]);
do hh--; while (arr[hh] > arr[low]);
if (hh < ll)
break;
SwapElements(arrptr + ll, arrptr + hh);
}
SwapElements(arrptr + low, arrptr + hh);
if (hh <= median)
low = ll;
if (hh >= median)
high = hh - 1;
}
}
}
私の5セント(より簡単/シンプルで、短いリストには十分に見えるため):
public static T Median<T>(this IEnumerable<T> items)
{
var i = (int)Math.Ceiling((double)(items.Count() - 1) / 2);
if (i >= 0)
{
var values = items.ToList();
values.Sort();
return values[i];
}
return default(T);
}
PSは、ShitalShahによって説明されている「より高い中央値」を使用しています。
以下のコードは機能しますが、あまり効率的ではありません。:(
static void Main(String[] args) {
int n = Convert.ToInt32(Console.ReadLine());
int[] medList = new int[n];
for (int x = 0; x < n; x++)
medList[x] = int.Parse(Console.ReadLine());
//sort the input array:
//Array.Sort(medList);
for (int x = 0; x < n; x++)
{
double[] newArr = new double[x + 1];
for (int y = 0; y <= x; y++)
newArr[y] = medList[y];
Array.Sort(newArr);
int curInd = x + 1;
if (curInd % 2 == 0) //even
{
int mid = (x / 2) <= 0 ? 0 : (newArr.Length / 2);
if (mid > 1) mid--;
double median = (newArr[mid] + newArr[mid+1]) / 2;
Console.WriteLine("{0:F1}", median);
}
else //odd
{
int mid = (x / 2) <= 0 ? 0 : (newArr.Length / 2);
double median = newArr[mid];
Console.WriteLine("{0:F1}", median);
}
}
}