2023-06-20：给定一个长度为N的数组arr，arr[i]表示宝石的价值

2023-06-20：给定一个长度为N的数组arr，arr[i]表示宝石的价值

你在某天遇到X价值的宝石，

X价值如果是所有剩余宝石价值中的最小值，你会将该宝石送人

X价值如果不是所有剩余宝石价值中的最小值，你会将该宝石放到所有宝石的最后

返回把宝石都送人需要多少天

比如arr = [3,1,4,3,1,2]

在第1天，你遇到了价值3的宝石，但是3并不是所有剩余宝石的价值最小值

所以你把3放在了所有宝石的最后，arr = [1,4,3,1,2,3]

在第2天，你遇到了价值1的宝石，1是所有剩余宝石的价值最小值

所以你把价值1的宝石送人，arr = [4,3,1,2,3]

在第3天，你把价值4的宝石放到最后，arr = [3,1,2,3,4]

在第4天，你把价值3的宝石放到最后，arr = [1,2,3,4,3]

在第5天，你送出了价值1的宝石，arr = [2,3,4,3]

在第6天，你送出了价值2的宝石，arr = [3,4,3]

在第7天，你送出了价值3的宝石，arr = [4,3]

在第8天，你把价值4的宝石放到最后，arr = [3,4]

在第9天，你送出了价值3的宝石，arr = [4]

在第10天，你送出了价值4的宝石，宝石已经没有了。

所以返回10。

1 <= N <= 10的5次方，

1 <= 宝石价值 <= 10的9次方。

来自TikTok美国笔试。

答案2023-06-20：

1.第一个方法(days1)使用了暴力的方式，通过遍历数组并移动宝石来模拟每一天的操作，直到所有宝石都被送出。时间复杂度较高。

2.第二个方法(days2)使用了更高效的算法。首先构建了一个支持查询累加和和最小值的数据结构（IndexTree和SegmentTree）。然后利用这些数据结构来计算送出所有宝石需要的天数。具体步骤如下：

2.1.初始化累加和数据结构(it)和最小值数据结构(st)。

2.2.设定起始位置(start)为1，找到剩余宝石中的最小值(find)。

2.3.计算从起始位置到最小值之间的宝石总数(daysCount)。

2.4.将最小值送出，更新累加和数据结构(it)和最小值数据结构(st)。

2.5.更新起始位置(start)为最小值。

2.6.重复上述步骤直到所有宝石都被送出。

2.7.返回送出宝石所需的天数。

时间复杂度和空间复杂度如下：

方法1（days1）：

• •时间复杂度：$O(N^2)$，其中N是宝石数组的长度。需要遍历数组N次，并且在每次操作中需要移动宝石，移动的次数也达到了N次。
• •空间复杂度：O(N)，需要额外的存储空间来存储宝石数组。

方法2（days2）：

• •时间复杂度：$O(N * (logN)^2)$，其中N是宝石数组的长度。构建IndexTree和SegmentTree所需的时间复杂度为O(N * logN)。每次查询最小值的时间复杂度为O(logN)，总共进行N次查询。因此，总的时间复杂度为$O(N * (logN)^2)$。
• •空间复杂度：O(N)，需要额外的存储空间来构建IndexTree和SegmentTree。

综上所述，方法1的时间复杂度为$O(N^2)$，方法2的时间复杂度为$O(N * (logN)^2)$。在时间复杂度上，方法2优于方法1。方法1的空间复杂度为O(N)，方法2的空间复杂度为O(N)。在空间复杂度上，两种方法相同。

go完整代码如下：

packagemain
import(
"fmt"
"math"
"math/rand"
"time"
)
//暴力方法
//为了验证
funcdays1(diamonds[]int)int{
arr:=make([]int,len(diamonds))
copy(arr,diamonds)
ans:=0
forlen(arr)>0{
ans++
deal(&arr)
}
returnans
}
//暴力方法
//为了验证
funcdeal(arr*[]int){
head:=(*arr)[0]
*arr=(*arr)[1:]
min:=head
for_,num:=range*arr{
min=int(math.Min(float64(min),float64(num)))
}
ifhead>min{
*arr=append(*arr,head)
}
}
//正式方法
//时间复杂度O(N*(logN)的平方)
funcdays2(diamonds[]int)int{
//n:位置
n:=len(diamonds)
//1~n:1
it:=NewIndexTree(n)
//762...
//123....
st:=NewSegmentTree(diamonds)
days:=0
find,start:=1,1
forit.SumRange(1,n)!=0{
//start.....find(后续....最小值，最左的位置)
find=findMin(st,start,n)
days+=daysCount(it,start,find,n)
//1
//find
it.Add(find,-1)
st.Update(find,math.MaxInt32)
start=find
}
returndays
}
funcfindMin(st*SegmentTree,start,nint)int{
//start....n左部分1~start-1右
varl,r,min=n,1,st.Min(1,n)
ifst.Min(start,n)==min{
l=start
r=n
}else{
l=1
r=start-1
}
varm,ans=-1,-1
forl<=r{
m=(l+r)/2
ifst.Min(l,m)==min{
ans=m
r=m-1
}else{
l=m+1
}
}
returnans
}
funcdaysCount(it*IndexTree,start,find,nint)int{
ifstart<=find{
returnit.SumRange(start,find)
}else{
returnit.SumRange(start,n)+it.SumRange(1,find)
}
}
//支持查询累加和
typeIndexTreestruct{
tree[]int
nint
}
funcNewIndexTree(sizeint)*IndexTree{
it:=&IndexTree{
tree:make([]int,size+1),
n:size,
}
fori:=1;i<=size;i++{
it.Add(i,1)
}
returnit
}
func(it*IndexTree)Sum(iint)int{
ret:=0
fori>0{
ret+=it.tree[i]
i-=i&-i
}
returnret
}
func(it*IndexTree)SumRange(l,rint)int{
returnit.Sum(r)-it.Sum(l-1)
}
func(it*IndexTree)Add(i,dint){
fori<=it.n{
it.tree[i]+=d
i+=i&-i
}
}
//支持查询最小值
typeSegmentTreestruct{
nint
min[]int
}
funcNewSegmentTree(arr[]int)*SegmentTree{
n:=len(arr)
st:=&SegmentTree{
n:n,
min:make([]int,(n+1)<<2),
}
fori:=1;i<=n;i++{
st.Update(i,arr[i-1])
}
returnst
}
func(st*SegmentTree)Update(i,vint){
st.update(i,i,v,1,st.n,1)
}
func(st*SegmentTree)update(L,R,C,l,r,rtint){
ifL<=l&&r<=R{
st.min[rt]=C
return
}
mid:=(l+r)>>1
ifL<=mid{
st.update(L,R,C,l,mid,rt<<1)
}
ifR>mid{
st.update(L,R,C,mid+1,r,rt<<1|1)
}
st.pushUp(rt)
}
func(st*SegmentTree)pushUp(rtint){
st.min[rt]=int(math.Min(float64(st.min[rt<<1]),float64(st.min[rt<<1|1])))
}
func(st*SegmentTree)Min(l,rint)int{
returnst.minQuery(l,r,1,st.n,1)
}
func(st*SegmentTree)minQuery(L,R,l,r,rtint)int{
ifL<=l&&r<=R{
returnst.min[rt]
}
mid:=(l+r)>>1
ans:=math.MaxInt32
ifL<=mid{
ans=int(math.Min(float64(ans),float64(st.minQuery(L,R,l,mid,rt<<1))))
}
ifR>mid{
ans=int(math.Min(float64(ans),float64(st.minQuery(L,R,mid+1,r,rt<<1|1))))
}
returnans
}
//为了测试
funcrandomArray(n,vint)[]int{
arr:=make([]int,n)
fori:=0;iarr[i]=rand.Intn(v)
}
returnarr
}
//为了测试
funcmain(){
rand.Seed(time.Now().UnixMilli())
fmt.Println("例子测试开始")
arr:=[]int{3,1,4,3,1,2}
fmt.Println(days1(arr))
fmt.Println(days2(arr))
fmt.Println("例子测试结束")
N:=100
V:=100000
testTimes:=1000
fmt.Println("随机测试开始")
fori:=0;in:=rand.Intn(N)+1
diamonds:=randomArray(n,V)
ans1:=days1(diamonds)
ans2:=days2(diamonds)
ifans1!=ans2{
fmt.Println("出错了!")
}
}
fmt.Println("随机测试结束")
fmt.Println("性能测试开始")
n:=100000
v:=1000000000
diamonds:=randomArray(n,V)
fmt.Println("宝石数量:",n)
fmt.Println("价值范围:",v)
start:=time.Now()
days2(diamonds)
end:=time.Now()
fmt.Println("运行时间:",end.Sub(start).Milliseconds(),"毫秒")
fmt.Println("性能测试结束")
}