给定数组，根据同一数组中其他值的条件对其进行排序。
给定数组，根据同一数组中其他值的条件对其进行排序。
提问于 2022-05-20 18:16:58
这是一个涉及数据结构和算法应用的问题。我无法在极客练习测试中解决这个问题。
问题：
有两个非整数数组，A和B。A由人的高度组成。A中每个人对应的数字B，这样，对于A中的每一个人，身高>= Ai的人的确切Bi数应该站在A中的人I的前面，然后根据这个条件对A进行排序。
我们应该按给定的方式安排A。
约束：
1 <= N(人数) <= 1000
1 <= Ai <= 10000
示例
- A =3 2 1
B=0 1 1
out =3 1 2
- A =5 3 2 6 1 4
B=0 1 2 0 3 2
out =5 3 2 1 6 4
回答 1
Stack Overflow用户
回答已采纳
发布于 2022-05-21 10:02:32
def linsert(ans,elt,ind):
for i in range(len(ans)):
if ans[i] == None:
ind -= 1
if ind == 0:
break
return i
def arrange(a,b,n):
ans = [None for i in range(n)]
for i in range(n):
a[i] = (a[i],i)
a.sort(key = lambda x : x[0])
for i in range(n):
elt = a[i][0]
ind = b[a[i][1]]
ind = linsert(ans,elt,ind)
ans[ind] = elt
return ans在上面的代码中，需要为最终的排序安排调用函数排列。
我们从@ start 3386109所指出的最小元素开始。我们将它放置在空数组ans中的posoition中，其中j是a中最小数的索引。我们反复这样做，直到所有的数字都被处理。在实践中，这是通过第一个排序A，然后插入在b[i]如果它是空的，其他循环在ans上寻找所有的空位置可以放置一个更大或相等的数字，然后放置我们的号码。如果可能的话，请随意优化。请随意将此翻译成其他语言。如果我使用的是C++，仅仅是因为方便，我只会使用一个pair<int,int>(elt,i)的min堆，其中我是原始未排序数组中的位置。然后，我会弹出堆，直到它是空的，并以与上面相同的方式放置元素。
由于在解决方案中的排序，成本是O(nlogn)。所需内存为O(n)，用于答案和索引。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/72323254
复制相关文章
相似问题
腾讯云开发者
