给定一个数组，根据同一数组中其他值的条件对其进行排序

Question

这是一道数据结构和算法应用题。我无法在 Geeks for Geeks 练习测试中解决它。

问题：
有 2 个非整数数组，A 和 B。A 由人的身高组成。 A中每个人对应的数字B，这样对于A中的每个人i，恰好B[i]个身高> = A[i]的人应该站在A中人i的前面，排序后按照这个条件。

我们应该按照给定的方式排列A。

约束条件：
1 <= N（人数）<= 1000
1 <= A[i] <= 10000

例子

A = [3 2 1]
B = [0 1 1]
输出 = [3 1 2]
A = [5 3 2 6 1 4]
B = [0 1 2 0 3 2]
输出 = [5 3 2 1 6 4]

Answer 1

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

上述代码中，需要调用函数arrange进行最终排序
正如@user3386109 所指出的，我们从最小的元素开始。我们将它放在一个空数组 ans 中的 b[j] 位置，其中 j 是 a 中最小数字的索引。我们反复这样做，直到处理完所有数字。实际上，这是通过首先对 A 进行排序，然后在 b[i] 处插入（如果它为空），否则遍历 ans 以找到所有可以放置大于或等于数字的空位置，然后放置我们的号码。如果可能，请随时对此进行优化。请随时将其翻译成其他语言。如果我使用 C++，仅仅为了方便，我会简单地使用 pair<int,int>(elt,i) 的最小堆，其中 i 是原始未排序数组中的位置。然后，我会弹出堆直到它为空，然后以与上面相同的方式放置元素。

由于解决方案中的排序，成本为O(nlogn)。所需内存为 O(n)，用于答案和索引。

给定一个数组，根据同一数组中其他值的条件对其进行排序

Given an array, sort it according to conditions on other values in the same array

sorting

algorithm

data-structures