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)>>1
if 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
}
关于上述代码的解释：（对于树状数组的简单解释）
为什么用树状数组？因为树状数组能够 logN 获取一个区间的前缀和，并能够 logN 的复杂度修改区间的值。
树状数组中，通过不断加上 lowbit 可以获得每个关键区间，让 [1, i] 区间增加或减少一个值（add 操作）
而通过不断减去 lowbit 可以获得区间和 [1, i]（pre 操作）
求 lowbit 的方法：i & -i
减去 lowbit 的方法：i &= i-1
什么是 lowbit？
=> 10010 中，10 就是 lowbit