Python程序：检查子数组能否重新排列成等差数列

假设我们有一组数字nums，以及另外两个大小为m的数组l和r，这些l和r表示范围查询，例如[l[i], r[i]]。我们需要找到一个布尔序列ans，其中ans[i]为真，当且仅当子数组nums[l[i]], nums[l[i] + 1], ... nums[r[i] - 1], nums[r[i]]可以重新排列成一个等差数列，否则为假。

如果一个数列至少包含两个元素，并且每两个连续元素之间的差相同，则称该数列为等差数列。例如，一些等差数列有：[2, 4, 6, 8, 10]，[5, 5, 5, 5]，[4, -2, -8, -14]，但[2, 2, 3, 6, 9]不是。

因此，如果输入类似于nums = [6,8,7,11,5,9]，l = [0,0,2]，r = [2,3,5]，则输出将为[True, False, True]，因为：

  • 对于查询[0, 2]，序列为[6,8,7]，可以重新排列为[6,7,8]，这是有效的。

  • 对于查询[0, 3]，序列为[6,8,7,11]，不能重新排列成等差数列。

  • 对于查询[2, 5]，序列为[7,11,5,9]，可以重新排列为[5,7,9,11]，这是有效的。

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

  • new := 一个与l大小相同的列表，并用全真值填充。

  • 对于i从0到l的大小-1，执行：

    • data := 从索引l[i]到r[i]的nums的子列表。

    • 对列表data进行排序。

    • d := 一个新列表。

    • 对于j从0到data的大小-2，执行：

      • 将data[j+1] - data[j]插入到d的末尾。

    • d := 从d的新集合创建的新列表。

    • 如果d的大小不等于1，则：

      • new[i] := False

  • 返回new

示例

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

Open Compiler
def solve(nums, l, r):
   new = [True]*len(l)

   for i in range(len(l)):
      data = nums[l[i]:r[i]+1]
      data.sort()

      d = []
      for j in range(len(data) - 1):
         d.append(data[j+1] - data[j])

      d = list(set(d))
      if len(d) != 1:
         new[i] = False
   return new

nums = [6,8,7,11,5,9]
l = [0,0,2]
r = [2,3,5]
print(solve(nums, l, r))

输入

[6,8,7,11,5,9], [0,0,2], [2,3,5]

Learn Python in-depth with real-world projects through our Python certification course. Enroll and become a certified expert to boost your career.

输出

[True,False,True]

更新于：2021年10月6日

121次浏览

开启你的职业生涯

完成课程获得认证

开始学习
广告