rustgym/leetcode/
_1296_divide_array_in_sets_of_k_consecutive_numbers.rs

1struct Solution;
2use std::collections::BTreeMap;
3use std::collections::VecDeque;
4
5impl Solution {
6    fn is_possible_divide(nums: Vec<i32>, k: i32) -> bool {
7        let n = nums.len();
8        let k = k as usize;
9        if n % k != 0 {
10            return false;
11        }
12        let mut btm: BTreeMap<i32, usize> = BTreeMap::new();
13        for x in nums {
14            *btm.entry(x).or_default() += 1;
15        }
16        let mut queue: VecDeque<(i32, usize)> = VecDeque::new();
17        for (val, size) in btm {
18            queue.push_back((val, size));
19            if queue.len() == k {
20                let (first_val, first_size) = queue.pop_front().unwrap();
21                for i in 1..k {
22                    let (next_val, next_size) = queue.pop_front().unwrap();
23                    if next_val != first_val + i as i32 {
24                        return false;
25                    }
26                    if next_size < first_size {
27                        return false;
28                    }
29                    if next_size > first_size {
30                        queue.push_back((next_val, next_size - first_size));
31                    }
32                }
33            }
34        }
35        queue.is_empty()
36    }
37}
38
39#[test]
40fn test() {
41    let nums = vec![1, 2, 3, 3, 4, 4, 5, 6];
42    let k = 4;
43    let res = true;
44    assert_eq!(Solution::is_possible_divide(nums, k), res);
45    let nums = vec![3, 2, 1, 2, 3, 4, 3, 4, 5, 9, 10, 11];
46    let k = 3;
47    let res = true;
48    assert_eq!(Solution::is_possible_divide(nums, k), res);
49    let nums = vec![3, 3, 2, 2, 1, 1];
50    let k = 3;
51    let res = true;
52    assert_eq!(Solution::is_possible_divide(nums, k), res);
53    let nums = vec![1, 2, 3, 4];
54    let k = 3;
55    let res = false;
56    assert_eq!(Solution::is_possible_divide(nums, k), res);
57}