Python程式：在遞減和重排後查詢最大元素

假設我們有一個名為arr的陣列。我們必須對arr執行一些操作，以使其滿足以下條件：

• arr中的第一個元素必須為1。

• 任何兩個相鄰元素之間的絕對差必須最多為1。

並且有兩種操作。我們可以任意次數地執行這兩種型別的操作：

• 將arr的任何值減小到較小的正數。

• 以任何順序重新排列arr的元素。

我們必須在執行操作以滿足給定條件後找到arr中可能的最大值。

因此，如果輸入類似於arr = [3,3,2,3,2]，則輸出將為3，因為我們可以將最後一個元素減小到1，然後將其重新排列為[1,2,3,3,3]，最大值為3。

為了解決這個問題，我們將遵循以下步驟：

• 對列表arr進行排序

• arr[0] := 1

• 對於範圍從1到arr大小-1的i，執行以下操作：

  • arr[i] := min(arr[i - 1] + 1, arr[i])

• 返回arr的最大值

示例

讓我們看看下面的實現，以便更好地理解：

def solve(arr):
   arr.sort()
   arr[0] = 1

   for i in range(1, len(arr)):
      arr[i] = min(arr[i - 1] + 1, arr[i])

   return max(arr)

arr = [3,3,2,3,2]
print(solve(arr))

輸入

[3,3,2,3,2]

輸出

3

Arnab Chakraborty

更新於：2021年10月8日

瀏覽量：159

開啟你的職業生涯

完成課程獲得認證

開始學習