2024-08-28：用go语言，给定一个从1开始、长度为n的整数数组nums

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.定义一个空数组和，并创建两个BinaryIndexedTree数据结构和。

arr1

arr2

tree1

tree2

3.对于数组中的每个元素：

nums

3.1. 将当前元素按照索引排序，并通过Binary Indexed Tree记录每个元素在排序后数组中的位置。

3.2. 进行前两次操作：将加入，将加入。

nums[0]

arr1

nums[1]

arr2

3.3. 从第三个元素开始遍历：

3.3.1.计算和中大于当前元素的个数，并根据规则选择将当前元素加入哪个数组，更新对应的Binary Indexed Tree。

arr1

arr2

4.返回将和连接而成的结果数组。

arr1

arr2

result

总的时间复杂度分析为O(n log n)，其中n为数组的长度。

nums

总的额外空间复杂度为O(n)，主要是用于存储排序后的数组、索引映射表、两个Binary Indexed Tree结构以及结果数组。

Go完整代码如下：

packagemain
import(
"fmt"
"sort"
)
typeBinaryIndexedTreestruct{
tree[]int
}
funcNewBinaryIndexedTree(nint)*BinaryIndexedTree{
return&BinaryIndexedTree{tree:make([]int,n+1)}
}
func(bit*BinaryIndexedTree)Add(iint){
foribit.tree[i]++
i+=i&-i
}
}
func(bit*BinaryIndexedTree)Get(iint)int{
sum:=0
fori>0{
sum+=bit.tree[i]
i-=i&-i
}
returnsum
}
funcresultArray(nums[]int)[]int{
n:=len(nums)
sortedNums:=make([]int,n)
copy(sortedNums,nums)
sort.Ints(sortedNums)
index:=make(map[int]int)
fori,num:=rangesortedNums{
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]])
fori:=2;icount1:=len(arr1)-tree1.Get(index[nums[i]])
count2:=len(arr2)-tree2.Get(index[nums[i]])
ifcount1>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...)
}
funcmain(){
nums:=[]int{2,1,3,3}
fmt.Println(resultArray(nums))
}

rust完整代码如下：

usestd::collections::HashMap;
structBinaryIndexedTree{
tree:Vec,
}
implBinaryIndexedTree{
fnnew(n:usize)->Self{
BinaryIndexedTree{tree:vec![0;n+1]}
}
fnadd(&mutself,muti:usize){
whileiself.tree[i]+=1;
i+=i&(!i+1);
}
}
fnget(&self,muti:usize)->i32{
letmutsum=0;
whilei>0{
sum+=self.tree[i];
i-=i&(!i+1);
}
sum
}
}
fnresult_array(nums:&mutVec)->Vec{
letn=nums.len();
letmutsorted_nums=nums.clone();
sorted_nums.sort();
letmutindex=HashMap::new();
for(i,&num)insorted_nums.iter().enumerate(){
index.insert(num,i+1);
}
letmutarr1=vec![nums[0]];
letmutarr2=vec![nums[1]];
letmuttree1=BinaryIndexedTree::new(n);
letmuttree2=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());
ifcount1>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());
}
}
letmutresult=vec![];
result.append(&mutarr1);
result.append(&mutarr2);
result
}
fnmain(){
letmutnums=vec![2,1,3,3];
println!("{:?}",result_array(&mutnums));
}