不使用额外空间的合并两个排序数组

2024 年 8 月 29 日 | 阅读 17 分钟

在此问题中，我们将得到两个已排序的数组。我们的任务是合并给定的两个数组。但是，限制条件是我们必须在不使用任何额外空间的情况下合并它们。因此，在排序数组后，初始元素将位于第一个数组中（根据第一个数组的初始容量），其余元素位于第二个数组中。

让我们看一些例子来理解程序的输入和输出。

示例

输入： array1 = [11], array2 = [3, 4]

输出： array1 = [2], array2 = [4, 11]

输入： array1 = [1, 6, 9, 11, 16, 21], array2 = [1, 4, 7, 13]

输出： array1 = [1, 1, 4, 6, 7, 9], array2 = [11, 13, 16, 21]

如果我们允许使用额外空间，这个问题将会很简单。然而，在没有额外空间的情况下解决这个问题会使问题变得复杂。

蛮力方法将以 O(m * n) 的时间复杂度解决此问题。但是，有更有效的方法来解决它。

方法 - 1

我们将采用此方法来解决此问题

我们将从第二个数组 array2 的最后一个元素开始迭代，并搜索它是否存在于 array1 中。如果我们发现 array1 中有一个元素大于该元素，我们将把最后一个元素移动到第一个数组 array1，而将另一个元素移动到 array2。为了保持两个数组的排序，我们必须将元素插入到正确的位置。我们可以使用插入排序算法来搜索这个正确的位置。

以下是解决此问题的算法方法

我们将从第二个数组的末尾开始迭代该数组的每个元素。
对于第二个数组的每个元素，执行以下步骤
- 我们将第一个数组的最后一个元素存储在一个变量中：last = array1[-1]
- 从第一个数组的倒数第二个元素开始迭代，直到我们满足条件 array1[j] < array2[i]。
- 现在我们将第一个数组的元素向后移动一个索引。
- 我们将检查第一个数组的最后一个元素是否大于第二个数组的最后一个元素，然后我们将交换这些位置的元素。
最后，我们将打印合并后的排序数组。
在第二个循环中，单个数组的元素始终保持排序状态。

以下是实现上述方法的 Python 程序。

代码

# Python program to show how to merge two sorted arrays without creating extra space.
 
# Defining the function that will take the two sorted arrays and return the two merged sorted arrays.
def merge(array1, array2, m, n):
 
  # Starting the loop that will iterate over the elements of the second array, starting from the last element
  for i in range(n - 1, -1, -1):

    # Now, we will find the smallest element in array1 greater than the current element of array2.
    # Once we find it, we will shift all elements of array1 and move one index ahead
    # This will be done till the required element of array1 is not found.

    last = array1[m - 1]
    j = m - 2
    while(j >= 0 and array1[j] > array2[i]):
      array1[j + 1] = array1[j]
      j -= 1
 
    # If we found the greater element
    if (last > array2[i]):
 
      array1[j + 1] = array2[i]
      array2[i] = last
 
# Creating two sample arras and calling the function
array1 = [1, 6, 9, 11, 16, 21]
array2 = [1, 4, 7, 13]
m = len(array1)
n = len(array2)

print("Initial First Array: ", end = "")
for i in range(m):
  print(array1[i], " ", end = "")
print()
print("Initial Second array: ", end = "")
for i in range(n):
  print(array2[i], " ", end = "")
print()
# Merging the arrays 
merge(array1, array2, m, n)

print("Merged First Array: ", end = "")
for i in range(m):
  print(array1[i], " ", end = "")
print()
print("Merged First Array: ", end = "")
for i in range(n):
  print(array2[i], " ", end = "")

输出

Initial First Array: 1 
6 9 11 
16 21  
Initial Second array: 1 
4 7 13  
Merged First Array: 1 
1 4 6 
7 9  
Merged First Array: 11 
13 16 21

时间复杂度：该程序需要 O(M * N) 来完成。时间复杂度是非线性的，因为我们在嵌套循环中迭代两个数组。

辅助空间：由于问题本身要求只使用常数额外空间来解决。因此，空间复杂度为 O(1)。

方法 - 2

现在我们将讨论另一种解决此问题的有效方法。

上述解决方案中存在一个重复的模式。当同时遍历两个已排序数组时，假设我们到达第二个已排序数组的第 j 个元素，它小于第一个已排序数组的第 i 个元素。那么在下一步，我们必须将第 j 个元素插入到第一个数组中，从第一个数组中移除某个第 k 个元素并将其插入到第二个数组中。我们将使用此模式来优化上述代码。

以下是我们为解决此问题将遵循的步骤

我们将初始化三个变量：i = 0, j = 0, k = n - 1。这里 n 是第一个数组的大小。
我们将迭代 array1 和 array2 的每个元素。但是，这次我们将使用每个数组的两个指针 i 和 j。
- 现在，如果第一个数组的第 i 个元素小于第二个数组的第 j 个元素，则递增 i。
- 否则，如果上述条件不满足，我们将用第二个数组的第 j 个元素替换第一个数组的第 k 个元素。将 i 增加 1 并将 k 减少 1。
最后一步是在交换两个元素后对单个数组进行排序，以保持顺序。

以下是上述算法的 Python 程序

代码

# Python program to show how to merge two sorted arrays without creating extra space.

# Defining a function to insert the element in the sorted array in the correct position using Insertion Sort
def insertionSort(arr):
     
    if (n := len(arr)) <= 1:
      return
    for i in range(1, n):
         
        key = arr[i]

        # Move elements of arr[0..i-1], that are
        # greater than key, to one position ahead
        # of their current position
        j = i-1
        while j >=0 and key < arr[j] :
                arr[j+1] = arr[j]
                j -= 1
        arr[j+1] = key

# Defining the function that will take the two sorted arrays and return the two merged sorted arrays.
def merge(array1, array2, m, n):

    # Initializing the three pointers that we need
    i = 0
    j = 0
    k = m - 1

    # Iterating over the two arrays using the while loop
    while (i <= k and j < n):

        # Checking the first condition, i.e., if the ith element of the first array is smaller than the jth element of the second array
        if (array1[i] < array2[j]):
            i += 1
        
        # If the above condition is not satisfied, swap the jth element of the second array and the kth element of the first array
        else:
            t = array2[j]
            array2[j] = array1[k]
            array1[k] = t
            j += 1
            k -= 1
   
insertionSort(array1)
   
insertionSort(array2)

# Creating two sample arras and calling the function
array1 = [1, 6, 9, 11, 16, 21]
array2 = [2, 4, 7, 13]
m = len(array1)
n = len(array2)

print("Initial First Array: ", end = "")
for i in range(m):
    print(array1[i], " ", end = "")
print()
print("Initial Second array: ", end = "")
for i in range(n):
    print(array2[i], " ", end = "")
print()
# Merging the arrays
merge(array1, array2, m, n)

print("Merged First Array: ", end = "")
for i in range(m):
    print(array1[i], " ", end = "")
print()
print("Merged Second Array: ", end = "")
for i in range(n):
    print(array2[i], " ", end = "")

输出

Initial First Array: 1 
6 9 11 
16 21  
Initial Second array: 2 
4 7 13  
Merged First Array: 1 
2 4 6 
7 9  
Merged Second Array: 11 
13 16 21

时间复杂度：该程序需要 O((N + M) * log(N + M)) 来完成。这里 N 和 M 是两个数组的大小。我们只遍历列表一次 (N + M)；但是，我们在每次迭代结束时对数组进行排序；因此，线性时间乘以 log(N + M)。

空间复杂度：由于程序不使用任何额外空间，因此为 O(1)。

方法 - 3

我们将使用此方法解决此问题

此方法将比较第一个数组的最后一个元素与第二个数组的第一个元素。现在，如果第一个数组的元素大于第二个数组的元素，我们将交换这两个元素。下一步是排序数组。第一个数组已经排序，但我们有第二个数组。我们必须重复这些步骤，直到第一个条件为真。在过程结束时，我们将得到两个已排序的数组。

我们将为这种方法遵循以下步骤。

我们将初始化一个变量 i 为 0。
我们将启动一个 while 循环，直到第一个数组的最后一个元素大于第二个数组的第一个元素。
- 如果第一个数组的第 i 个元素大于第二个数组的第一个元素。
- 我们将交换两个数组的第 i 个元素和第 0 个元素。
- 然后我们将对第二个数组进行排序。
- 下一步是将 i 增加 1。
最后，我们将打印两个数组。

以下是使用上述方法的 Python 程序，用于解决此问题。

代码

# Python program to show how to merge two sorted arrays without creating extra space.
 
# Defining the function that will take the two sorted arrays and return the two merged sorted arrays.
def merge(array1, array2, m, n):
  i = m - 1
  t = 0
 
  # Starting the while loop, which will run until the last element of the first array is greater than the first element of the second array
  while (array1[m - 1] > array2[0]):
    if (array1[i] > array2[0]):
      # If the condition holds, then we will swap the two elements.
      # After this, the second array will be unsorted, so will sort that array
      # Array 1 is already sorted.
      t = array1[i]
      array1[i] = array2[0]
      array2[0] = t
      array2.sort()
    # Incrementing i by 1
    i += 1

# Creating two sample arras and calling the function
array1 = [1, 6, 9, 11, 16, 21]
array2 = [1, 4, 7, 13]
m = len(array1)
n = len(array2)

print("Initial First Array: ", end = "")
for i in range(m):
  print(array1[i], " ", end = "")
print()
print("Initial Second array: ", end = "")
for i in range(n):
  print(array2[i], " ", end = "")
print()
# Merging the arrays
merge(array1, array2, m, n)

print("Merged First Array: ", end = "")
for i in range(m):
  print(array1[i], " ", end = "")
print()
print("Merged First Array: ", end = "")
for i in range(n):
  print(array2[i], " ", end = "")

输出

Initial First Array: 1 
6 9 11 
16 21  
Initial Second array: 1 
4 7 13  
Merged First Array: 1 
1 4 6 
7 9  
Merged First Array: 11 
13 16 21

时间复杂度：该程序的时间复杂度为 O(M * (N * logN))。这里 M 和 N 是两个数组的大小。LogN 的时间复杂度是在每次迭代结束时对第二个数组进行排序。

辅助空间：空间复杂度与 O(1) 相同。

方法 - 4

以下是解决此问题的另一种方法。

我们将以较短数组的长度为 N，以较大数组的长度为 M。
我们将取较短的数组并找到应从中划分它的索引。
我们必须在较短数组的中值所在的位置进行划分。(m1)
现在我们将取第二个数组的前 M - m1 个元素。
我们将比较边界元素。
- 如果 m1 元素小于 f1 元素且 l2 元素小于 f2 元素，那么我们就找到了索引。
- 否则，如果 m1 元素大于 f2 元素，那么我们需要在左子数组中搜索。
- 否则，我们将在右子数组中搜索。
下一步是将所有较小的元素存储在长度较短的数组中。
直到索引 i，我们将较短数组的所有元素与较大数组的前 M - i 个元素进行交换。
下一步是对两个数组进行排序。
如果第一个数组的长度大于第二个数组的长度，那么所有较小的元素都将移到第一个数组中。
然后我们将较大数组逆时针旋转 N 次。
最后一步是交换两个数组的前 N 个元素。

以下是实现上述方法的 Python 代码。

代码

# Python program to merge the given two sorted arrays without taking any extra space.
 
# Defining a function to rotate the array.
def rotate(a, n, i):
  for j in range((i // 2)):
    a[j], a[i - 1 - i] = a[i - 1 - i], a[j]
  for j in range(i, ((n + i) // 2)):
    a[j], a[n - 1 - (j - i)] = a[n - 1 - (j - i)], a[j]
  for i in range((n // 2)):
    a[j], a[n - 1 - j] = a[n - 1 - j], a[j]
 
# Defining a function to shift the smaller elements to the first array
def shift(arr1, arr2, m, n):
  l = 0
  h = m - 1
  index = 0
  while (l <= h):
    m1 = ((l + h) // 2)
    m2 = m - m1 - 1
    l1 = arr1[m1]
    l2 = arr2[m2 - 1]
    h1 = sys.maxint if m1 == m - 1 else arr1[m1 + 1]
    h2 = sys.maxint if m2 == n else arr2[m2]
    if l1 > h2:
      h = m1 - 1
      if h == -1:
        index = 0
    elif l2 > h1:
      l = m1 + 1
      if l == m - 1:
        index = m
    else:
      index = m1 + 1
      break
  for i in range(index, m):
    arr1[i], arr2[i - index] = arr2[i - index], arr1[i]

  # Sorting the two arrays
  arr1.sort()
  arr2.sort()
 
# Main function to sort the two arrays
def merge(arr1, arr2, m, n):
  if m > n:
    shift(arr2, arr1, n, m)
    rotate(arr1, m, m - n)
    for i in range(n):
      arr1[i], arr2[i] = arr2[i], arr1[i]
  else:
    shift(arr1, arr2, n, m)
# Driver program
 
 
# Creating two sample arras and calling the function
array1 = [1, 6, 9, 11, 16, 21]
array2 = [1, 4, 7, 13]
m = len(array1)
n = len(array2)

print("Initial First Array: ", end = "")
for i in range(m):
  print(array1[i], " ", end = "")
print()
print("Initial Second array: ", end = "")
for i in range(n):
  print(array2[i], " ", end = "")
print()
# Merging the arrays
merge(array1, array2, n, m)

print("Merged First Array: ", end = "")
for i in range(m):
  print(array1[i], " ", end = "")
print()
print("Merged First Array: ", end = "")
for i in range(n):
  print(array2[i], " ", end = "")

输出

Initial First Array: 1 
6 9 11 
16 21  
Initial Second array: 1 
4 7 13  
Merged First Array: 1 
1 4 6 
7 9  
Merged First Array: 11 
13 16 21

时间复杂度：该程序需要 O(max(M * logM, N * logN)) 来完成。这里 log 的时间复杂度是在每次迭代后对两个数组进行排序。

空间复杂度：该程序将占用恒定的额外空间。因此，为 O(1)

方法 - 5

在此方法中，我们将使用插入排序合并两个已排序的数组。

在上述程序中，当我们向其他数组插入元素时，我们可以使用插入排序来插入元素，因为其余数组已经排序。这将进一步降低程序的时空复杂度。因此，在交换两个元素时，我们必须将交换的元素放置在适当的位置，以便数组仍然是排序的。这可以通过单次遍历来完成。

以下是我们为解决此问题将遵循的步骤

我们将通过持续将第一个列表与第二个列表的第一个元素进行比较来对第一个列表进行排序。如果第二个列表的元素大于第一个列表的元素，那么我们将交换这两个元素。
当我们交换一个元素时，我们将使用插入排序方法将交换的元素插入到第二个列表中。这样，元素将始终插入到正确的位置，并且在迭代结束时，第二个列表将始终是排序的。
由于我们执行交换，如果我们发现第二个列表的元素大于第一个列表的元素，那么交换这两个元素将始终使第一个列表保持排序状态。但是，通过执行插入排序，我们可以维护第二个列表的顺序。

以下是使用上述方法解决此问题的 Python 程序。

代码

# Python program to merge two sorted arrays using insertion sort

# Defining a function that will take two sorted arrays and return the two merged sorted arrays
def merge(array1, array2):
  e = len(array1)
  i = 0

  # Iterating over the first sorted array
  while(i < e):

    # If we find an element of the second array that is smaller than the element in the first array, then we will swap the two elements
    if(array1[i] > array2[0]):
      swap(array1, array2, i, 0)

      # We will use insertion sort here to insert the element of the first array to the correct position of the second array
      insert(array2, 0)

    # Incrementing to the next element      
    i += 1

# Defining a function that will perform insertion sort
def insert(array, i):
  o = array[i]
  i += 1
  # It will search for the correct position to insert the element so that the array remains sorted
  while (i < len(array) and array[i] < o):
    array[i - 1] = array[i]
    i += 1
  array[i - 1] = o

# Defining a function to swap the two elements of the arrays
def swap(array1, array2, i, j):
  temp = array1[i]
  array1[i] = array2[j]
  array2[j] = temp

# Creating two sample arras and calling the function
array1 = [1, 6, 9, 11, 16, 21]
array2 = [1, 4, 7, 13]

print("Initial First Array: ", end = "")
print(array1)
print("Initial Second array: ", end = "")
print(array2)

# Merging the arrays
merge(array1, array2)

print("Merged First Array: ", end = "")
print(array1)
print("Merged First Array: ", end = "")
print(array2)

输出

Initial First Array: [1, 6, 9, 11, 16, 21]
Initial Second array: [1, 4, 7, 13]
Merged First Array: [1, 1, 4, 6, 7, 9]
Merged First Array: [11, 13, 16, 21]

时间复杂度：该程序具有非线性时间复杂度。时间复杂度为 O(M * N)。这里，M 和 N 是两个给定数组的长度。

空间复杂度：空间复杂度是所需的常数空间复杂度。因此，为 O(1)。

方法 - 6

在此方法中，我们将使用欧几里得除法引理来合并两个数组。该引理陈述为 (((Operation_on_array) % A) * A)

以下是我们为解决此问题需要遵循的步骤

我们将使用与合并排序时相同的合并数组的方法。但是，这次我们将同时使用欧几里得除法引理和之前的方法。
合并两个数组后，我们将用 A 除以它们。
这里 A 是一个大于两个数组中所有元素的数字。
在我们的问题中，数组元素没有上限。为了保持通用性，我们将 A 取为 10e7 + 1。

以下是使用欧几里得除法引理解决此问题的 Python 程序。

代码

# Python3 program to merge two sorted arrays using Euclidean Division Lemma
 
# Defining a function that will take two sorted arrays and return the two merged sorted arrays
def merge(array1, array2, n, m):

  # Initiating the pointers to iterate the arrays
  i = 0
  j = 0
  k = 0

  # Storing the constant for the Euclidean division lemma
  a = 10e7 + 1

  # In the first loop, we will arrange the elements of the first array
  while i < n and (j < n and k < m):

    # If both the first and the second arrays are modified
    if array1[j] >= a and array2[k] >= a:
      if array1[j] % a <= array2[k] % a:
        array1[i] += (array1[j] % a) * a
        j += 1
      else:
        array1[i] += (array2[k] % a) * a
        k += 1
    
    # If the first array is modified but not the second array
    elif array1[j] >= a:
      if array1[j] % a <= array2[k]:
        array1[i] += (array1[j] % a) * a
        j += 1
      else:
        array1[i] += (array2[k] % a) * a
        k += 1
    # If the second array is modified but not the first array
    elif array2[k] >= a:
      if array1[j] <= array2[k] % a:
        array1[i] += (array1[j] % a) * a
        j += 1
      else:
        array1[i] += (array2[k] % a) * a
        k += 1
    
    # If none of the array's numbers are modified
    else:
      if array1[j] <= array2[k]:
        array1[i] += (array1[j] % a) * a
        j += 1
      else:
        array1[i] += (array2[k] % a) * a
        k += 1
    i += 1
 
  # Since the first array is already modified completely, we just need to modify the second array
  while j < n and i < n:
    array1[i] += (array1[j] % a) * a
    i += 1
    j += 1
  while k < m and i < n:
    array1[i] += (array2[k] % a) * a
    i += 1
    k += 1

  i = 0
 
  # Now, we have to arrange the elements of the second array
  while i < m and (j < n and k < m):

    # If both the first and the second arrays are modified
    if array1[j] >= a and array2[k] >= a:
      if array1[j] % a <= array2[k] % a:
        array2[i] += (array1[j] % a) * a
        j += 1
 
      else:
        array2[i] += (array2[k] % a) * a
        k += 1
 
    # If the first array is modified but not the second array
    elif array1[j] >= a:
      if array1[j] % a <= array2[k]:
        array2[i] += (array1[j] % a) * a
        j += 1
 
      else:
        array2[i] += (array2[k] % a) * a
        k += 1
 
    # If the second array is modified but not the first array
    elif array2[k] >= a:
      if array1[j] <= array2[k] % a:
        array2[i] += (array1[j] % a) * a
        j += 1
 
      else:
        array2[i] += (array2[k] % a) * a
        k += 1
 
    else:
      # If none of the array's numbers are modified
      if array1[j] <= array2[k]:
        array2[i] += (array1[j] % a) * a
        j += 1
 
      else:
        array2[i] += (array2[k] % a) * a
        k += 1
 
    i += 1
  # Since the second array is already modified completely, we just need to modify the first array
  while j < n and i < m:
    array2[i] += (array1[j] % a) * a
    i += 1
    j += 1
 
  while k < m and i < m:
    array2[i] += (array2[k] % a) * a
    i += 1
    k += 1
 
  i = 0
  
  
  # In the last step, we will divide every element of the first array by a
  while i < n:
    array1[i] /= a
    i += 1
 
  i = 0
  # Now, we will divide every element of the second array by a
  while i < m:
    array2[i] /= a
    i += 1
 
# Creating two sample arras and calling the function
array1 = [1, 6, 9, 11, 16, 21]
array2 = [1, 4, 7, 13]
m = len(array1)
n = len(array2)

print("Initial First Array: ", end = "")
for i in range(m):
  print(array1[i], " ", end = "")
print()
print("Initial Second array: ", end = "")
for i in range(n):
  print(array2[i], " ", end = "")
print()
# Merging the arrays
merge(array1, array2, m, n)

print("Merged First Array: ", end = "")
for i in range(m):
  print(int(array1[i]), " ", end = "")
print()
print("Merged First Array: ", end = "")
for i in range(n):
  print(int(array2[i]), " ", end = "")

输出

Initial First Array: 1 
6 9 11 
16 21  
Initial Second array: 1 
4 7 13  
Merged First Array: 1 
1 4 6 
7 9  
Merged First Array: 11 
13 16 21

时间复杂度：由于我们使用线性循环，该程序的时空复杂度为 O(M + N)

空间复杂度： O(1)

下一主题Python 中的二项分布

← 上一个下一个 →

不使用额外空间的合并两个排序数组

方法 - 1

方法 - 2

方法 - 3

方法 - 4

方法 - 5

方法 - 6

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

Python 问题

不使用额外空间的合并两个排序数组

方法 - 1

方法 - 2

方法 - 3

方法 - 4

方法 - 5

方法 - 6

相关帖子

Python 中的简单 FLAMES 游戏

Python 中的 re.sub() 函数

Python 中的梯度下降优化器

Python 无穷大

如何使用 Python 获取国家信息

在 Python 中验证 IP 地址

Python 中的语法和拼写检查器

使用 Scikit-Learn 在 Python 中查找欧几里得距离

使用卷积神经网络进行花朵识别

Python 音频模块

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器