2024-12-12：找出唯一性数组的中位数。用go语言，给定一个整数数组 nums，找出唯一性数组并计算其中位数。

唯一性数组是一个按元素从小到大排序的数组，包含了所有 nums 的非空子数组中不同元素的个数。

中位数定义为有序数组的中间元素，如果有两个中间元素则取较小的那个。

1 <= nums.length <= 100000。

1 <= nums[i] <= 100000。

输入：nums = [3,4,3,4,5]。

输出：2。

解释：

nums 的唯一性数组为 [1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3] 。唯一性数组的中位数为 2 ，因此答案是 2 。

答案2024-12-12：

chatgpt[1]

题目来自leetcode3134。

大体步骤如下：

1.首先定义了一个函数medianOfUniquenessArray，接受一个整数数组nums作为参数，返回计算得到的中位数。

2.在该函数中，通过计算median值，确定应该在唯一性数组中寻找的元素。

3.定义了一个内部函数check(t int) bool，用于检查数组中不同元素数目小于等于 t 的连续子数组数目是否大于等于 median。

4.在check函数中，创建了一个map cnt 来统计不同元素出现的次数，用 tot 记录遍历过的子数组数量。

5.使用双指针i和j来维护子数组范围，其中i向前遍历，j向后收缩。

6.通过二分查找的方式，在区间[1, n]内找到合适的t值，使得check函数返回true，确定当前的唯一性数组包含中位数。

7.最终返回找到的res作为结果。

总的时间复杂度：O(nlogn)，其中n为数组nums的长度，因为在二分查找过程中每次都通过check函数来判断需要的t值，每次check函数的时间复杂度为O(n)。

总的额外空间复杂度：O(n)，主要用于存储不同元素出现次数的map cnt。

Go完整代码如下：package mainimport ( "fmt")func medianOfUniquenessArray(nums []int) int { n := len(nums) median := (int64(n)*int64(n+1)/2 + 1) / 2 // 检测数组中不同元素数目小于等于 t 的连续子数组数目是否大于等于 median check := func(t int) bool { cnt := make(map[int]int) tot := int64(0) for i, j := 0, 0; i < n; i++ { cnt[nums[i]]++ for len(cnt) > t { cnt[nums[j]]-- if cnt[nums[j]] == 0 { delete(cnt, nums[j]) } j++ } tot += int64(i - j + 1) } return tot >= median } res := 0 lo, hi := 1, n for lo <= hi { mid := (lo + hi) / 2 if check(mid) { res = mid hi = mid - 1 } else { lo = mid + 1 } } return res}func main() { nums := []int{3, 4, 3, 4, 5} fmt.Println(medianOfUniquenessArray(nums))}

Rust完整代码如下：use std::collections::HashMap;fn median_of_uniqueness_array(nums: Vec<i32>) -> i32 { let n = nums.len() as i64; let median = (n * (n + 1) / 2 + 1) / 2; // 检测数组中不同元素数目小于等于 t 的连续子数组数目是否大于等于 median let check = |t: i32| { let mut cnt = HashMap::new(); let mut tot = 0; let (mut j, mut i) = (0, 0); while i < n { *cnt.entry(nums[i as usize]).or_insert(0) += 1; while cnt.len() > t as usize { let entry = cnt.entry(nums[j as usize]).or_insert(0); *entry -= 1; if *entry == 0 { cnt.remove(&nums[j as usize]); } j += 1; } tot += i - j + 1; i += 1; } tot >= median }; let mut res = 0; let (mut lo, mut hi) = (1, n as i32); while lo <= hi { let mid = (lo + hi) / 2; if check(mid) { res = mid; hi = mid - 1; } else { lo = mid + 1; } } res}fn main() { let nums = vec![3, 4, 3, 4, 5]; println!("{}", median_of_uniqueness_array(nums));}

引用链接

[1] chatgpt: https://chatbotsplace.com/?rc=nnNWSCJ7EP