2022-05-07：返回一个数组中，所有降序三元组的数量。

2022-05-07：返回一个数组中，所有降序三元组的数量。

比如 : {5, 3, 4, 2, 1}，

所有降序三元组为 :

{5, 3, 2}、{5, 3, 1}、{5, 4, 2}、{5, 4, 1}、

{5, 2, 1}、{3, 2, 1}、{4, 2, 1}。

所以返回数量7。

答案2022-05-07：

利用index tree。

时间复杂度：O(N * logN)。

空间复杂度：O(N)。

代码用rust编写。代码如下：

代码语言：rust复制

fn main() {
    let mut arr: Vec<isize> = vec![5, 3, 4, 2, 1];
    let answer = num1(&mut arr);
    println!("answer = {}", answer);

    let mut arr: Vec<isize> = vec![5, 3, 4, 2, 1];
    let answer = num2(&mut arr);
    println!("answer = {}", answer);
}

fn num1(arr: &mut Vec<isize>) -> isize {
    if arr.len() < 3 {
        return 0;
    }
    let mut path: Vec<isize> = vec![0, 0, 0];
    return process(arr, 0, &mut path, 0);
}

fn process(arr: &mut Vec<isize>, index: isize, path: &mut Vec<isize>, size: isize) -> isize {
    if size == 3 {
        return if path[0] > path[1] && path[1] > path[2] {
            1
        } else {
            0
        };
    }
    let mut ans: isize = 0;
    if index < arr.len() as isize {
        ans = process(arr, index   1, path, size);
        path[size as usize] = arr[index as usize];
        ans  = process(arr, index   1, path, size   1);
    }
    return ans;
}

// 正式方法
// 时间复杂度O(N * logN)
// 利用index tree
fn num2(arr: &mut Vec<isize>) -> isize {
    if arr.len() < 3 {
        return 0;
    }
    let n: isize = arr.len() as isize;
    let mut sorted: Vec<isize> = vec![];
    for i in 0..n {
        sorted.push(arr[i as usize])
    }
    sorted.sort_unstable();
    let mut max: isize = -9223372036854775808;
    for i in 0..n {
        arr[i as usize] = rank(&mut sorted, arr[i as usize]);
        max = get_max(max, arr[i as usize]);
    }
    let mut it2: IndexTree = IndexTree::new(max);
    let mut it3: IndexTree = IndexTree::new(max);
    let mut ans: isize = 0;
    let mut i: isize = n - 1;
    while i >= 0 {
        ans  = if arr[i as usize] == 1 {
            0
        } else {
            it3.sum(arr[i as usize] - 1)
        };
        it2.add(arr[i as usize], 1);
        it3.add(
            arr[i as usize],
            if arr[i as usize] == 1 {
                0
            } else {
                it2.sum(arr[i as usize] - 1)
            },
        );
        i -= 1;
    }
    return ans;
}

fn get_max(a: isize, b: isize) -> isize {
    if a > b {
        a
    } else {
        b
    }
}

// 返回>=num, 最左位置
fn rank(sorted: &mut Vec<isize>, num: isize) -> isize {
    let mut l: isize = 0;
    let mut r: isize = sorted.len() as isize - 1;
    let mut m: isize;
    let mut ans: isize = 0;
    while l <= r {
        m = (l   r) / 2;
        if sorted[m as usize] >= num {
            ans = m;
            r = m - 1;
        } else {
            l = m   1;
        }
    }
    return ans   1;
}

pub struct IndexTree {
    pub tree: Vec<isize>,
    pub n: isize,
}

// 下标从1开始
impl IndexTree {
    // 0位置弃而不用
    pub fn new(n: isize) -> IndexTree {
        let mut tree: Vec<isize> = vec![];
        for _i in 0..n   1 {
            tree.push(0)
        }
        IndexTree { tree: tree, n: n }
    }
    // 1~index 累加和是多少？
    pub fn sum(&self, index: isize) -> isize {
        let mut index: isize = index;
        let mut ret: isize = 0;
        while index > 0 {
            ret  = self.tree[index as usize];
            index -= index & -index;
        }
        return ret;
    }
    pub fn add(&mut self, index: isize, d: isize) {
        let mut index: isize = index;
        while index <= self.n {
            self.tree[index as usize]  = d;
            index  = index & -index;
        }
    }
}

执行结果如下：

在这里插入图片描述

左神java代码

java rust tree 数组

0 人点赞