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

開啟你的職業生涯

完成課程獲得認證

開始學習