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

福大大架构师每日一题

发布于 2024-12-19 18:40:03

10400

代码可运行

文章被收录于专栏：福大大架构师每日一题福大大架构师每日一题

运行总次数：0

代码可运行

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 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]]++
forlen(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;

fnmedian_of_uniqueness_array(nums:Vec<i32>)->i32{
letn= nums.len()asi64;
letmedian=(n *(n +1)/2+1)/2;

// 检测数组中不同元素数目小于等于 t 的连续子数组数目是否大于等于 median
letcheck=|t:i32|{
letmut cnt=HashMap::new();
letmut tot=0;
let(mut j,mut i)=(0,0);

while i < n {
*cnt.entry(nums[i asusize]).or_insert(0)+=1;

while cnt.len()> t asusize{
letentry= cnt.entry(nums[j asusize]).or_insert(0);
*entry -=1;
if*entry ==0{
                    cnt.remove(&nums[j asusize]);
}
                j +=1;
}
            tot += i - j +1;
            i +=1;
}

        tot >= median
};

letmut res=0;
let(mut lo,mut hi)=(1, n asi32);

while lo <= hi {
letmid=(lo + hi)/2;

ifcheck(mid){
            res = mid;
            hi = mid -1;
}else{
            lo = mid +1;
}
}

    res
}

fnmain(){
letnums=vec![3,4,3,4,5];
println!("{}",median_of_uniqueness_array(nums));
}