Python程序：查找数组第一次拆分后，小于另一列表元素的最小长度

假设我们有一个数字列表nums，我们想将列表分成两部分part1和part2，使得part1中的每个元素都小于或等于part2中的每个元素。我们必须找到可能的part1的最小长度（非0长度）。

因此，如果输入类似于nums = [3, 1, 2, 5, 4]，则输出将为3，因为我们可以将列表拆分为part1 = [3, 1, 2]和part2 = [5, 4]。

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

• p := nums的最小值
• s := 0
• 对于i从0到nums的大小-1，执行：
  • 如果nums[i]等于p，则
    • s := i
    • 退出循环
• p := nums子列表（从索引0到s）的最大值
• ans := s
• 对于i从s+1到nums的大小-1，执行：
  • 如果nums[i] < p，则
    • ans := i
• 返回ans + 1

示例

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

def solve(nums):
   p = min(nums)
   s = 0
   for i in range(len(nums)):
      if nums[i] == p:
         s = i
         break
   p = max(nums[: s + 1])
   ans = s
   for i in range(s + 1, len(nums)):
      if nums[i] < p:
         ans = i
   return ans + 1

nums = [3, 1, 2, 5, 4]
print(solve(nums))

输入

[3, 1, 2, 5, 4]

输出

3

Arnab Chakraborty

更新于：2021年10月19日

浏览量：155

开启你的职业生涯

完成课程获得认证

开始学习