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 mainimport("fmt""sort")typeBinaryIndexedTreestruct{ 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 :=0for 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]])}}returnappend(arr1, arr2...)}func main(){ nums :=[]int{2,1,3,3} fmt.Println(resultArray(nums))}

在这里插入图片描述

rust完整代码如下：use std::collections::HashMap;structBinaryIndexedTree{ tree:Vec<i32>,}implBinaryIndexedTree{fnnew(n:usize)->Self{BinaryIndexedTree{ tree:vec![0; n+1]}}fnadd(&mutself,mut i:usize){while i <self.tree.len(){self.tree[i]+=1; i += i &(!i +1);}}fnget(&self,mut i:usize)->i32{letmut sum=0;while i >0{ sum +=self.tree[i]; i -= i &(!i +1);} sum}}fnresult_array(nums:&mutVec<i32>)->Vec<i32>{letn= nums.len();letmut sorted_nums= nums.clone(); sorted_nums.sort();letmut index=HashMap::new();for(i,&num)in sorted_nums.iter().enumerate(){ index.insert(num, i +1);}letmut arr1=vec![nums[0]];letmut arr2=vec![nums[1]];letmut tree1=BinaryIndexedTree::new(n);letmut tree2=BinaryIndexedTree::new(n); tree1.add(*index.get(&nums[0]).unwrap()); tree2.add(*index.get(&nums[1]).unwrap());foriin2..n {letcount1= arr1.len()asi32- tree1.get(*index.get(&nums[i]).unwrap());letcount2= arr2.len()asi32- 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());}}letmut result=vec![]; result.append(&mut arr1); result.append(&mut arr2); result}fnmain(){letmut nums=vec![2,1,3,3];println!("{:?}",result_array(&mut nums));}

在这里插入图片描述