讨论/求职面试/面试题求解/

题目描述

有两组数,第⼀组数顺序固定,请编程实现让第⼆组数 相邻数字间的⼤⼩关系和第⼀组数相同,并且第⼆组相邻数字间的差值之和最⼤,求这个最大差值和。 两个数组长度一样


示例

示例:比如 A=[4, 8, 7, 9, 3] B=[1, 2, 3, 4, 5] 给B按照A相邻的元素大小关系排序 然后B所有元素间距(正数)的和要求最大 其中一个B的排序结果为[2, 5, 1, 4, 3] 间距和为: abs(2-5) + abs(5-1) + abs(1-4) + abs(4-3) = 11


def same_order(array1: List[int], array2: List[int]) -> int:
    """
    :param array1: 目标顺序数组
    :param array2: 待排序数组
    :return: 最大间距和
    """

7
共 1 个回复

最优解,应当是找出第一个数组里所有的波峰和波谷。在填充第二个数组的时候,将最大的值依次填到波峰,将最小的值依次填到波谷,把其余的值以任意方式填满空闲位置即可(需要在波峰和波谷之间保持单调)。

注意细节:
最大值优先装填左边和右边都有数的波峰,最小值优先装填左边和右边都有数的波谷。
这些波峰/波谷填充完后,再去填充出现在数组最左侧和最右侧的位置。

def same_order(array1: list, array2: list) -> int:
    """
    :param array1: 目标顺序数组
    :param array2: 待排序数组
    :return: 最大间距和
    """
    level=[0]*len(array1)
    for i in range(len(array1)):
        if i-1>=0:
            level[i]+=1 if array1[i-1]<array1[i] else -1
        if i+1<len(array1):
            level[i]+=1 if array1[i+1]<array1[i] else -1

    indexes=sorted(range(len(array1)),key=lambda idx:(level[idx],array1[idx]))
    return [pair[1] for pair in sorted(list(zip(indexes,sorted(array2))))]