Struct leetcode_for_rust::cd0703_kth_largest_element_in_a_stream::KthLargest

pub struct KthLargest;

Solutions

Approach 1: BinaryHeap

• Time complexity: O(log2 k)

• Space complexity: O(1)

use std::collections::BinaryHeap;

struct KthLargest {
    k: usize,
    heap: BinaryHeap<i32>,
}

impl KthLargest {
    fn new(k: i32, nums: Vec<i32>) -> Self {
        let mut kth = KthLargest { k: k as usize, heap: BinaryHeap::new(), };
        for n in nums {
            kth.add(n);
        }
        kth
    }

    fn add(&mut self, val: i32) -> i32 {
        if self.heap.len() < self.k || *self.heap.peek().unwrap() >= -val {
            self.heap.push(-val);
            if self.heap.len() > self.k {
                self.heap.pop();
            }
        }
        -*self.heap.peek().unwrap()
    }
}

Approach 2: Vec

• Time complexity: O(n log n)

• Space complexity: O(1)

struct KthLargest {
    k: usize,
    v: Vec<i32>,
}

impl KthLargest {
    fn new(k: i32, nums: Vec<i32>) -> Self {
        let mut kth = KthLargest { k: k as usize, v: Vec::new(), };
        for n in nums {
            kth.add(n);
        }
        kth
    }

    fn add(&mut self, val: i32) -> i32 {
        if self.v.len() < self.k || Some(self.v.last().unwrap()) < Some(&val) {
            self.v.push(val);
            self.v.sort_unstable_by(|a, b| b.cmp(a));
            if self.v.len() > self.k {
                self.v.pop();
            }
        }

        *self.v.last().unwrap()
    }
}