3134. Find the Median of the Uniqueness Array Hard

1/**
2 * [3134] Find the Median of the Uniqueness Array
3 *
4 * You are given an integer array nums. The uniqueness array of nums is the sorted array that contains the number of distinct elements of all the <span data-keyword="subarray-nonempty">subarrays</span> of nums. In other words, it is a sorted array consisting of distinct(nums[i..j]), for all 0 <= i <= j < nums.length.
5 * Here, distinct(nums[i..j]) denotes the number of distinct elements in the subarray that starts at index i and ends at index j.
6 * Return the median of the uniqueness array of nums.
7 * Note that the median of an array is defined as the middle element of the array when it is sorted in non-decreasing order. If there are two choices for a median, the smaller of the two values is taken.<!-- notionvc: 7e0f5178-4273-4a82-95ce-3395297921dc -->
8 *  
9 * <strong class="example">Example 1:
10 * <div class="example-block">
11 * Input: <span class="example-io">nums = [1,2,3]</span>
12 * Output: <span class="example-io">1</span>
13 * Explanation:
14 * The uniqueness array of nums is [distinct(nums[0..0]), distinct(nums[1..1]), distinct(nums[2..2]), distinct(nums[0..1]), distinct(nums[1..2]), distinct(nums[0..2])] which is equal to [1, 1, 1, 2, 2, 3]. The uniqueness array has a median of 1. Therefore, the answer is 1.
15 * </div>
16 * <strong class="example">Example 2:
17 * <div class="example-block">
18 * Input: <span class="example-io">nums = [3,4,3,4,5]</span>
19 * Output: <span class="example-io">2</span>
20 * Explanation:
21 * The uniqueness array of nums is [1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3]. The uniqueness array has a median of 2. Therefore, the answer is 2.
22 * </div>
23 * <strong class="example">Example 3:
24 * <div class="example-block">
25 * Input: <span class="example-io">nums = [4,3,5,4]</span>
26 * Output: <span class="example-io">2</span>
27 * Explanation:
28 * The uniqueness array of nums is [1, 1, 1, 1, 2, 2, 2, 3, 3, 3]. The uniqueness array has a median of 2. Therefore, the answer is 2.
29 * </div>
30 *  
31 * Constraints:
32 * 
33 * 	1 <= nums.length <= 10^5
34 * 	1 <= nums[i] <= 10^5
35 * 
36 */
37pub struct Solution {}
38
39// problem: https://leetcode.com/problems/find-the-median-of-the-uniqueness-array/
40// discuss: https://leetcode.com/problems/find-the-median-of-the-uniqueness-array/discuss/?currentPage=1&orderBy=most_votes&query=
41
42// submission codes start here
43
44impl Solution {
45    pub fn median_of_uniqueness_array(nums: Vec<i32>) -> i32 {
46        0
47    }
48}
49
50// submission codes end
51
52#[cfg(test)]
53mod tests {
54    use super::*;
55
56    #[test]
57    fn test_3134() {
58    }
59}
60