amazon oa 里面的minimum parcels cost 那道题

I want to ask the question about minimum parcels cost in amazon oa

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

(nlogn)

I have attached the image below

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

匿名用户 发表于 2022-8-15 10:33
1. If len(parcels) == k, return 0.
2. Add all parcels to a Set parcelSet.
3. additionalCost = 0

谢谢你的线性解决方案

lc 2195

刚刚想到一个时间N空间1的方法。
用类似linear search的方法把数分成比k小的部分和比k大的部分，判断parcels[i] 和 i + (k - length)的关系，如果大说明左侧空间有余从左侧继续搜索，如果小说明左侧空间不足要在右侧继续搜索。
描述不怎么准确，有空了写段代码

1. def linearSearch(arr, left, right, target):
   
2.     leftIndex = left
   
3.     for rightIndex in range(left, right):
   
4.         if (arr[rightIndex] < target):
   
5.             arr[leftIndex], arr[rightIndex] = arr[rightIndex], arr[leftIndex]
   
6.             leftIndex += 1
   
7.     return leftIndex
   
8. 
   
9. def func(parcels, k):
   
10.     left, right, target = 0, len(parcels), k
    
11.     while left < right:
    
12.         index = this.linearSearch(parcels, left, right, target)
    
13.         if parcels[index] - index - 1 <= k - length:
    
14.             left = index
    
15.             target = target * 3 // 2
    
16.         else:
    
17.             right = index
    
18.             target // = 2
    
19.     return left * (left + 1) // 2 + sum(parcels[left:]) - sum(parcels)
    

复制代码

也许有bug或edge上的问题，不想检查了

补充内容 (2022-08-19 06:06 +8:00):
敲了一半发现一个bug，代码不给我存下来，来回折腾三遍，等我有空了复现一下交上去

南宫狗剩 发表于 2022-8-18 13:59
也许有bug或edge上的问题，不想检查了

补充内容 (2022-08-19 06:06 +8:00):

O(n^2) ?