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

题目来自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 main

import (
	"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));
}