dsalgo/
counting_array_rank.rs

1pub fn array_rank(mut a: Vec<usize>) -> Vec<usize> {
2    let n = a.len();
3
4    let mut m = *a.iter().min().unwrap();
5
6    for i in 0..n {
7        a[i] -= m;
8    }
9
10    m = *a.iter().max().unwrap();
11
12    let mut arg = vec![0; m + 2];
13
14    for &x in a.iter() {
15        arg[x + 1] += 1;
16    }
17
18    for i in 0..m + 1 {
19        arg[i + 1] += arg[i];
20    }
21
22    let mut res = vec![0; n];
23
24    for i in 0..n {
25        res[i] = arg[a[i]];
26
27        arg[a[i]] += 1;
28    }
29
30    res
31}
32
33#[cfg(test)]
34
35mod tests {
36
37    use super::*;
38
39    #[test]
40
41    fn test() {
42        let a = vec![7, 2, 1, 3, 2, 1];
43
44        assert_eq!(array_rank(a), [5, 2, 0, 4, 3, 1]);
45    }
46}