2024-08-28：用 go 语言，给定一个从 1 开始、长度为 n 的整数数组 nums，定义一个函数 greaterCount(arr, val)可以返回数组 arr 中大于 val 的元素数量。
按照以下规则进行 n 次操作，将 nums 中的元素分配到两个数组 arr1 和 arr2 中：
1.第一次操作将 nums[1]加入 arr1。
2.第二次操作将 nums[2]加入 arr2。
3.对于第 i 次操作：
3.1.如果 arr1 中大于 nums[i]的元素数量比 arr2 中大于 nums[i]的元素数量多，将 nums[i]加入 arr1。
3.2.如果 arr1 中大于 nums[i]的元素数量比 arr2 中大于 nums[i]的元素数量少，将 nums[i]加入 arr2。
3.3.如果 arr1 和 arr2 中大于 nums[i]的元素数量相等，将 nums[i]加入元素数量较少的数组。
3.4.如果仍然相等，则将 nums[i]加入 arr1。
将 arr1 和 arr2 连接起来形成结果数组 result。
要求返回整数数组 result。
输入：nums = [2,1,3,3]。
输出：[2,3,1,3]。
解释：在前两次操作后，arr1 = [2] ，arr2 = [1] 。
在第 3 次操作中，两个数组中大于 3 的元素数量都是零，并且长度相等，因此，将 nums[3] 追加到 arr1 。
在第 4 次操作中，两个数组中大于 3 的元素数量都是零，但 arr2 的长度较小，因此，将 nums[4] 追加到 arr2 。
在 4 次操作后，arr1 = [2,3] ，arr2 = [1,3] 。
因此，连接形成的数组 result 是 [2,3,1,3] 。
答案 2024-08-28：
chatgpt
题目来自 leetcode3072。
大体步骤如下：
1.创建一个新的函数greaterCount(arr, val)，用于计算数组arr中大于val的元素数量。
2.定义一个空数组arr1和arr2，并创建两个 BinaryIndexedTree 数据结构tree1和tree2。
3.对于数组nums中的每个元素：
3.1. 将当前元素按照索引排序，并通过 Binary Indexed Tree 记录每个元素在排序后数组中的位置。
3.2. 进行前两次操作：将nums[0]加入arr1，将nums[1]加入arr2。
3.3. 从第三个元素开始遍历：
3.3.1.计算arr1和arr2中大于当前元素的个数，并根据规则选择将当前元素加入哪个数组，更新对应的 Binary Indexed Tree。
4.返回将arr1和arr2连接而成的结果数组result。
总的时间复杂度分析为 O(n log n)，其中 n 为数组nums的长度。
总的额外空间复杂度为 O(n)，主要是用于存储排序后的数组、索引映射表、两个 Binary Indexed Tree 结构以及结果数组。
Go 完整代码如下：
package main
import ( "fmt" "sort")
type BinaryIndexedTree struct { tree []int}
func NewBinaryIndexedTree(n int) *BinaryIndexedTree { return &BinaryIndexedTree{tree: make([]int, n+1)}}
func (bit *BinaryIndexedTree) Add(i int) { for i < len(bit.tree) { bit.tree[i]++ i += i & -i }}
func (bit *BinaryIndexedTree) Get(i int) int { sum := 0 for i > 0 { sum += bit.tree[i] i -= i & -i } return sum}
func resultArray(nums []int) []int { n := len(nums) sortedNums := make([]int, n) copy(sortedNums, nums) sort.Ints(sortedNums) index := make(map[int]int) for i, num := range sortedNums { index[num] = i + 1 }
arr1, arr2 := []int{nums[0]}, []int{nums[1]} tree1, tree2 := NewBinaryIndexedTree(n), NewBinaryIndexedTree(n) tree1.Add(index[nums[0]]) tree2.Add(index[nums[1]])
for i := 2; i < n; i++ { count1 := len(arr1) - tree1.Get(index[nums[i]]) count2 := len(arr2) - tree2.Get(index[nums[i]]) if count1 > count2 || (count1 == count2 && len(arr1) <= len(arr2)) { arr1 = append(arr1, nums[i]) tree1.Add(index[nums[i]]) } else { arr2 = append(arr2, nums[i]) tree2.Add(index[nums[i]]) } }
return append(arr1, arr2...)}
func main() {
nums := []int{2, 1, 3, 3} fmt.Println(resultArray(nums))}
复制代码
rust 完整代码如下：
use std::collections::HashMap;
struct BinaryIndexedTree { tree: Vec<i32>,}
impl BinaryIndexedTree { fn new(n: usize) -> Self { BinaryIndexedTree { tree: vec![0; n+1] } }
fn add(&mut self, mut i: usize) { while i < self.tree.len() { self.tree[i] += 1; i += i & (!i + 1); } }
fn get(&self, mut i: usize) -> i32 { let mut sum = 0; while i > 0 { sum += self.tree[i]; i -= i & (!i + 1); } sum }}
fn result_array(nums: &mut Vec<i32>) -> Vec<i32> { let n = nums.len(); let mut sorted_nums = nums.clone(); sorted_nums.sort(); let mut index = HashMap::new(); for (i, &num) in sorted_nums.iter().enumerate() { index.insert(num, i + 1); }
let mut arr1 = vec![nums[0]]; let mut arr2 = vec![nums[1]]; let mut tree1 = BinaryIndexedTree::new(n); let mut tree2 = BinaryIndexedTree::new(n);
tree1.add(*index.get(&nums[0]).unwrap()); tree2.add(*index.get(&nums[1]).unwrap());
for i in 2..n { let count1 = arr1.len() as i32 - tree1.get(*index.get(&nums[i]).unwrap()); let count2 = arr2.len() as i32 - tree2.get(*index.get(&nums[i]).unwrap()); if count1 > count2 || (count1 == count2 && arr1.len() <= arr2.len()) { arr1.push(nums[i]); tree1.add(*index.get(&nums[i]).unwrap()); } else { arr2.push(nums[i]); tree2.add(*index.get(&nums[i]).unwrap()); } }
let mut result = vec![]; result.append(&mut arr1); result.append(&mut arr2); result}
fn main() { let mut nums = vec![2, 1, 3, 3]; println!("{:?}", result_array(&mut nums));}
复制代码
评论