Skip to content

Commit 3cb4f3f

Browse files
author
linzhijun
committed
fix
1 parent 771171c commit 3cb4f3f

1 file changed

Lines changed: 78 additions & 31 deletions

File tree

‎csharp/ToolGood.Algorithm/Internals/Functions/MathSum/Function_MEDIAN.cs‎

Lines changed: 78 additions & 31 deletions
Original file line numberDiff line numberDiff line change
@@ -1,39 +1,87 @@
1-
using System;
1+
using System;
22
using System.Collections.Generic;
33
using ToolGood.Algorithm.Enums;
44

55
namespace ToolGood.Algorithm.Internals.Functions.MathSum
66
{
77
internal sealed class Function_MEDIAN : Function_N
8-
{
9-
public Function_MEDIAN(FunctionBase[] funcs) : base(funcs)
10-
{
11-
if (funcs.Length < 1) {
12-
throw new ArgumentException($"Function '{Name}' requires at least 1 parameter.");
13-
}
14-
}
15-
16-
public override string Name => "Median";
17-
18-
public override Operand Evaluate(AlgorithmEngine engine, Func<AlgorithmEngine, string, Operand> tempParameter)
19-
{
20-
var args = new List<Operand>(funcs.Length);
21-
var error = TryEvaluateAll(engine, tempParameter, args);
22-
if(error != null) { return error; }
23-
24-
var list = new List<decimal>();
25-
var o = FunctionUtil.FlattenToList(args, list);
26-
27-
if (o == false) { return FunctionError(); }
28-
if (list.Count == 0) { return FunctionError(); }
29-
30-
list.Sort();
31-
var mid = list.Count / 2;
32-
if (list.Count % 2 == 0) {
33-
return Operand.Create((list[mid - 1] + list[mid]) / 2);
34-
}
35-
return Operand.Create(list[mid]);
36-
}
8+
{
9+
public Function_MEDIAN(FunctionBase[] funcs) : base(funcs)
10+
{
11+
if(funcs.Length < 1) {
12+
throw new ArgumentException($"Function '{Name}' requires at least 1 parameter.");
13+
}
14+
}
15+
16+
public override string Name => "Median";
17+
18+
public override Operand Evaluate(AlgorithmEngine engine, Func<AlgorithmEngine, string, Operand> tempParameter)
19+
{
20+
var args = new List<Operand>(funcs.Length);
21+
var error = TryEvaluateAll(engine, tempParameter, args);
22+
if(error != null) { return error; }
23+
24+
var list = new List<decimal>();
25+
if(FunctionUtil.FlattenToList(args, list) == false) { return FunctionError(); }
26+
if(list.Count == 0) { return FunctionError(); }
27+
28+
int n = list.Count;
29+
if(n == 1) return Operand.Create(list[0]);
30+
31+
int mid = n / 2;
32+
if(n % 2 == 0) {
33+
return Operand.Create((QuickSelect(list, mid - 1) + QuickSelect(list, mid)) / 2);
34+
}
35+
return Operand.Create(QuickSelect(list, mid));
36+
}
37+
38+
private static decimal QuickSelect(List<decimal> arr, int k)
39+
{
40+
int left = 0, right = arr.Count - 1;
41+
while(left < right) {
42+
int pivot = SelectPivot(arr, left, right);
43+
int partition = Partition(arr, left, right, pivot);
44+
if(partition == k) {
45+
return arr[k];
46+
}
47+
if(k < partition) {
48+
right = partition - 1;
49+
} else {
50+
left = partition + 1;
51+
}
52+
}
53+
return arr[left];
54+
}
55+
56+
private static int SelectPivot(List<decimal> arr, int left, int right)
57+
{
58+
int mid = left + (right - left) / 2;
59+
decimal a = arr[left], b = arr[mid], c = arr[right];
60+
if(a < b) {
61+
if(b < c) return mid;
62+
if(a < c) return right;
63+
return left;
64+
}
65+
if(a < c) return left;
66+
if(b < c) return right;
67+
return mid;
68+
}
69+
70+
private static int Partition(List<decimal> arr, int left, int right, int pivotIndex)
71+
{
72+
decimal pivot = arr[pivotIndex];
73+
(arr[pivotIndex], arr[right]) = (arr[right], arr[pivotIndex]);
74+
int storeIndex = left;
75+
for(int i = left; i < right; i++) {
76+
if(arr[i] < pivot) {
77+
(arr[storeIndex], arr[i]) = (arr[i], arr[storeIndex]);
78+
storeIndex++;
79+
}
80+
}
81+
(arr[storeIndex], arr[right]) = (arr[right], arr[storeIndex]);
82+
return storeIndex;
83+
}
84+
3785
public override OperandType GetResultType()
3886
{
3987
return OperandType.NUMBER;
@@ -50,5 +98,4 @@ internal override void GetParameterTypes(NoneEngine noneEngine, List<ParameterTy
5098
}
5199
}
52100
}
53-
54101
}

0 commit comments

Comments
 (0)