Skip to content

Commit 34520e1

Browse files
vJechsmayrvJechsmayr
authored
Merge pull request vJechsmayr#78 from eriksape/median
Median
2 parents 3152f14 + db85a87 commit 34520e1

14 files changed

Lines changed: 133 additions & 0 deletions

File tree

‎DataStructures/Binary Tree/Algorithms_toDo.txt‎

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,3 @@
1+
+ avl tree
2+
+ basic binary tree
3+
+ binary search tree

‎DataStructures/Hashing/Algorithms_toDo.txt‎

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,3 @@
1+
+ double hash
2+
+ hash table
3+
+ hash table with linked list

‎DataStructures/Linked List/Algorithms_toDo.txt‎

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,4 @@
1+
+ linked list
2+
+ double linked list
3+
+ is palindrome
4+
+ sqap nodes

‎DataStructures/Number Theory/Algorithms_toDo.txt‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1 @@
1+
+ prime numbers

‎DataStructures/Queue/Algorithms_toDo.txt‎

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,3 @@
1+
+ queue on list
2+
+ queue on pseudo stack
3+
+ double ended queue

‎DataStructures/Stacks/Algorithms_toDo.txt‎

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,4 @@
1+
+ stack
2+
+ next greater element
3+
+ postfix evaluation
4+
+ balanced parentheses

‎DynamicProgramming/Algorithms_toDo.txt‎

Lines changed: 19 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,19 @@
1+
+ abbreviation
2+
+ bitmask
3+
+ blimbing stairs
4+
+ coin change
5+
+ edit distance
6+
+ factorial
7+
+ fast fibonacci
8+
+ fibonacci
9+
+ floyd warshall
10+
+ integer partition
11+
+ longest commen subsequence
12+
+ longest increasing subsequence
13+
+ longest sub array
14+
+ matrix chain order
15+
+ max sub array
16+
+ minimum partition
17+
+ rod cutting
18+
+ subset generation
19+
+ sum of subset

‎Hashes/Algorithms_toDo.txt‎

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,4 @@
1+
+ Chaos Machine
2+
+ enigma Machine
3+
+ md5
4+
+ sha1

‎Maths/Algorithms_toDo.txt‎

Lines changed: 11 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,11 @@
1+
+ absolute
2+
+ average mean
3+
+ average median
4+
+ fibonacci
5+
+ fibonacci sequence recursion
6+
+ find max
7+
+ find min
8+
+ gaussian
9+
+ is square free
10+
+ prime check
11+
+ prime factors

‎Maths/AverageMedian.js‎

Lines changed: 50 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,50 @@
1+
const AverageMedian = function(arr1, arr2) {
2+
3+
const CalculateMedian = arr => (
4+
arr.length % 2 === 0
5+
? (arr[arr.length/2 - 1] + arr[arr.length/2])/2
6+
: arr[(arr.length + 1)/2 - 1]
7+
);
8+
9+
if(arr1.length === 0) {
10+
return CalculateMedian(arr2);
11+
}
12+
if(arr2.length === 0) {
13+
return CalculateMedian(arr1);
14+
}
15+
16+
let mergedArray = [];
17+
let mergedArrayLength = arr1.length + arr2.length;
18+
19+
let medianLimit = mergedArrayLength % 2 === 0 ? (mergedArrayLength/2 + 1) : (mergedArrayLength + 1)/2;
20+
let n1Count = 0, n2Count = 0;
21+
22+
while(mergedArray.length < medianLimit) {
23+
24+
if(n1Count >= arr1.length) {
25+
mergedArray.push(arr2[n2Count]);
26+
n2Count++;
27+
continue;
28+
}
29+
30+
if(n2Count >= arr2.length) {
31+
mergedArray.push(arr1[n1Count]);
32+
n1Count++;
33+
continue;
34+
}
35+
36+
if(arr1[n1Count] <= arr2[n2Count]) {
37+
mergedArray.push(arr1[n1Count]);
38+
n1Count++;
39+
} else {
40+
mergedArray.push(arr2[n2Count]);
41+
n2Count++;
42+
}
43+
}
44+
45+
if(mergedArrayLength % 2 === 0) {
46+
return (mergedArray[medianLimit-1] + mergedArray[medianLimit-2])/2;
47+
} else {
48+
return mergedArray[medianLimit-1];
49+
}
50+
};

0 commit comments

Comments
 (0)