两个已排序数组的就地排序，将前 n 项存储在第一个数组中，其余项存储在另一个数组中

Question

问题解释： 在这个问题中，给你两个长度为 n 和 m 的整数数组。这些数组按升序排序。我们希望您将给定数字中的 n 个最小元素存储在第一个数组中，并将其余数字存储在第二个数组中。 （请注意，您实现的算法应该就位。） 输入的第一行按顺序提供数字 n 和 m。在接下来的两行中，首先给出第一个数组的元素，然后给出第二个数组的元素。 0<=n,m<=1000 The output of your program should display the requested elements from the first array initially in the first line, followed by the elements of the second array in the next line. Note that your output should be sorted. Example:

Input:
5 3
1 4 7 8 10
2 3 9

Output:
1 2 3 4 7
8 9 10

请注意，您提供的代码的时间复杂度不得超过 O(m.n)。 我坚持认为这必须是就地解决方案。 我的解决方案： 我实际上已经提出了以下解决方案，并且使用了合并排序。但问题是没有到位。 任何可以指导我克服这个问题的提示或链接将不胜感激。 代码： '''

def merge_sort(array):

    if len(array) <= 1:
        return array

    mid = len(array) // 2
    left_half = array[:mid]
    right_half = array[mid:]

    left_half = merge_sort(left_half)
    right_half = merge_sort(right_half)

    return merge(left_half, right_half)

def merge(left, right):
    merged = []
    left_index = 0
    right_index = 0

    while left_index < len(left) and right_index < len(right):
        if left[left_index] <= right[right_index]:
            merged.append(left[left_index])
            left_index += 1
        else:
            merged.append(right[right_index])
            right_index += 1

    while left_index < len(left):
        merged.append(left[left_index])
        left_index += 1

    while right_index < len(right):
        merged.append(right[right_index])
        right_index += 1

    return merged

def store_nsmallest_elements(array1, array2, n, m):
    sorted_array = merge_sort(array1 + array2)
    return sorted_array[:n], sorted_array[n:n+m]

n, m = map(int, input().split())
array1 = list(map(int, input().split()))
array2 = list(map(int, input().split()))

first, second = store_nsmallest_elements(array1, array2, n, m)

print(*first)
print(*second)

'''

Answer 1

最简单的解决方案是为

len

/

get

/

set

定义适用于两个数组的自定义函数，然后实现自定义就地排序（例如冒泡排序、插入排序等）。这是插入排序的示例：

# return a length of arr1 + arr2
def custom_len(arr1, arr2):
    return len(arr1) + len(arr2)


# return a value from arr1/arr2 at index i (treat the two arrays as one big array)
def custom_get(arr1, arr2, i):
    if i < len(arr1):
        return arr1[i]
    return arr2[i - len(arr1)]

# set value val in arr1/arr2 at index i (treat the two arrays as one big array)
def custom_set(arr1, arr2, i, val):
    if i < len(arr1):
        arr1[i] = val
    else:
        arr2[i - len(arr1)] = val


def insertion_sort(arr1, arr2):
    n = custom_len(arr1, arr2)

    for i in range(1, n):
        key = custom_get(arr1, arr2, i)
        j = i - 1

        while j >= 0 and key < custom_get(arr1, arr2, j):
            custom_set(arr1, arr2, j + 1, custom_get(arr1, arr2, j))
            j -= 1

        custom_set(arr1, arr2, j + 1, key)


array1 = [1, 4, 7, 8, 10]
array2 = [2, 3, 9]

insertion_sort(array1, array2)

print(array1)
print(array2)

打印：

[1, 2, 3, 4, 7]
[8, 9, 10]