当前位置：首页 > news >正文

【LeetCode】每日一题 2024_6_4 将元素分配到两个数组中 II（二分、离散化、树状数组）

news 2025/6/27 19:48:23

文章目录

LeetCode？启动！！！
题目：将元素分配到两个数组中 II
- 题目描述
- 代码与解题思路
每天进步一点点

LeetCode？启动！！！

在这里插入图片描述
又有段时间没写每日一题的分享了，原本今天是打算早上发完晨起计划之后发的，但是今天太忙了，忙着忙着一直没时间把文章写完，拖着拖着就拖到晚上了

只能在晚上离散数学的课上悄摸摸写完发了

题目：将元素分配到两个数组中 II

题目链接：将元素分配到两个数组中 II

题目描述

代码与解题思路

// 树状数组
type fenwick []int// 维护 [1, i] 的元素个数
func (f fenwick) add(i int) {for ; i < len(f); i += i & -i {f[i]++}
}// 获取 [1, i] 的元素个数和
func (f fenwick) pre(i int) (res int) {for ; i > 0; i &= i - 1 {res += f[i]}return res
}func resultArray(nums []int) []int {// 排序去重 -> 离散化sorted := slices.Clone(nums)slices.Sort(sorted)sorted = slices.Compact(sorted)m := len(sorted)a, b := []int{nums[0]}, []int{nums[1]}// 维护树状数组t1, t2 := make(fenwick, m+1), make(fenwick, m+1)for i, v := range sorted {if v == nums[0] {t1.add(i+1)} if v == nums[1] {t2.add(i+1)}}for _, x := range nums[2:] {// 二分查找离散化数组的下标位置l, r := 0, len(sorted)for l < r {mid := (l+r)>>1if sorted[mid] < x {l = mid+1} else {r = mid}}v := l+1// greaterCount: 用数组所有元素 - 小于等于 val 元素的数量 = 大于 val 元素的数量gc1 := len(a) - t1.pre(v)gc2 := len(b) - t2.pre(v)if gc1 > gc2 || gc1 == gc2 && len(a) <= len(b) {a = append(a, x)t1.add(v)} else {b = append(b, x)t2.add(v)}}return append(a, b...)
}

代码的核心思路比较短，题目比较好理解（看着像是一个简单的模拟题）但是他给到的数据范围是 10^5，也就是他没法用暴力的算法去做

根据题目需要维护大于某个数的元素个数的要求，以及 10^9 次方的数字大小，我们可以用离散化 + 维护树状数组解决

两个问题

1）如何离散化？

sorted := slices.Clone(nums)
slices.Sort(sorted)
sorted = slices.Compact(sorted)

排序去重好的 sorted 数组，假设是 [ 7, 12, 23, 40 ]，我们在 nums 数组找到 23 这个元素的时候，就能根据这个元素在 sorted 数组中的位置，求的有 2 个数比他小，1 个数比他大

这就是离散化的意义

2）树状数组？

// 树状数组
type fenwick []int// 维护 [1, i] 的元素个数
func (f fenwick) add(i int) {for ; i < len(f); i += i & -i {f[i]++}
}// 获取 [1, i] 的元素个数和
func (f fenwick) pre(i int) (res int) {for ; i > 0; i &= i - 1 {res += f[i]}return res
}