【LeetCode】每日一题 2024_6_4 将元素分配到两个数组中 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
}

关于上述代码的解释：（对于树状数组的简单解释）

为什么用树状数组？因为树状数组能够 logN 获取一个区间的前缀和，并能够 logN 的复杂度修改区间的值。

树状数组中，通过不断加上 lowbit 可以获得每个关键区间，让 [1, i] 区间增加或减少一个值（add 操作）

而通过不断减去 lowbit 可以获得区间和 [1, i]（pre 操作）

求 lowbit 的方法：i & -i

减去 lowbit 的方法：i &= i-1

什么是 lowbit？

=> 10010 中，10 就是 lowbit

每天进步一点点

可以和我刷一辈子的每日一题吗？
一题一题，积累起来就是一辈子。