-
Notifications
You must be signed in to change notification settings - Fork 224
/
mode_sorted.js
63 lines (60 loc) · 2.18 KB
/
mode_sorted.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
/**
* The [mode](https://en.wikipedia.org/wiki/Mode_%28statistics%29) is the number
* that appears in a list the highest number of times.
* There can be multiple modes in a list: in the event of a tie, this
* algorithm will return the most recently seen mode.
*
* This is a [measure of central tendency](https://en.wikipedia.org/wiki/Central_tendency):
* a method of finding a typical or central value of a set of numbers.
*
* This runs in `O(n)` because the input is sorted.
*
* @param {Array<number>} sorted a sample of one or more data points
* @returns {number} mode
* @throws {Error} if sorted is empty
* @example
* modeSorted([0, 0, 1]); // => 0
*/
function modeSorted(sorted) {
// Handle edge cases:
// The mode of an empty list is undefined
if (sorted.length === 0) {
throw new Error("mode requires at least one data point");
} else if (sorted.length === 1) {
return sorted[0];
}
// This assumes it is dealing with an array of size > 1, since size
// 0 and 1 are handled immediately. Hence it starts at index 1 in the
// array.
let last = sorted[0],
// store the mode as we find new modes
value = NaN,
// store how many times we've seen the mode
maxSeen = 0,
// how many times the current candidate for the mode
// has been seen
seenThis = 1;
// end at sorted.length + 1 to fix the case in which the mode is
// the highest number that occurs in the sequence. the last iteration
// compares sorted[i], which is undefined, to the highest number
// in the series
for (let i = 1; i < sorted.length + 1; i++) {
// we're seeing a new number pass by
if (sorted[i] !== last) {
// the last number is the new mode since we saw it more
// often than the old one
if (seenThis > maxSeen) {
maxSeen = seenThis;
value = last;
}
seenThis = 1;
last = sorted[i];
// if this isn't a new number, it's one more occurrence of
// the potential mode
} else {
seenThis++;
}
}
return value;
}
export default modeSorted;