重庆有哪些做网站公司好,做公司网站的流程,深圳招聘信息在哪个网站,社团网站模板文章目录 LeetCode#xff1f;启动#xff01;#xff01;#xff01;题目#xff1a;将元素分配到两个数组中 II题目描述代码与解题思路 每天进步一点点 LeetCode#xff1f;启动#xff01;#xff01;#xff01; 又有段时间没写每日一题的分享了#xff0c;原本今… 文章目录 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, m1), make(fenwick, m1)for i, v : range sorted {if v nums[0] {t1.add(i1)} if v nums[1] {t2.add(i1)}}for _, x : range nums[2:] {// 二分查找离散化数组的下标位置l, r : 0, len(sorted)for l r {mid : (lr)1if sorted[mid] x {l mid1} else {r mid}}v : l1// 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
每天进步一点点 可以和我刷一辈子的每日一题吗 一题一题积累起来就是一辈子。
