在 Python 中查找需要 k 次合并排序调用的数组

server side programmingprogrammingpython

假设我们有两个数字 a 和 b，我们必须找到一个包含范围 [1, a] 内值的数组，并且需要调用递归合并排序函数的 b 次。

因此，如果输入为 a = 10，b = 15，则输出将为 [3,1,4,6,2,8,5,9,10,7]

为了解决这个问题，我们将遵循以下步骤 −

定义一个函数 resolve() 。这将需要 left、right、array、b
如果 b < 1 或 left + 1 与 right 相同，则
- 返回
b := b - 2
mid := (left + right) / 2
temp := array[mid - 1]
array[mid-1] := array[mid]
array[mid] := temp
solve(left, mid, array, b)
solve(mid, right, array, b)
从主方法执行以下操作 −
如果 b mod 2 与 0 相同，则
- 显示"无"
- 返回
array := 一个数组大小为 n + 1，并用 0 填充
array[0] := 1
对于范围从 1 到 a 的 i，执行
- array[i] := i + 1
b := b - 1
solve(0, a, array, b)
返回数组 a

示例

让我们看看下面的实现以便更好地理解 −

def solve(left,right,array,b):
   if (b < 1 or left + 1 == right):
      return
   b -= 2
   mid = (left + right) // 2
   temp = array[mid - 1]
   array[mid-1] = array[mid]
   array[mid] = temp
   solve(left, mid, array, b)
   solve(mid, right, array, b)
def find_arr(a,b):
   if (b % 2 == 0):
      print("None")
      return
   array = [0 for i in range(a + 2)]
   array[0] = 1
   for i in range(1, a):
      array[i] = i + 1
   b -=1
   solve(0, a, array, b)
return array, a
a = 10
b = 15
array, size = find_arr(a, b)
print(array[:size])