資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
Microsoft Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學Python程式：求使首尾元素對和相等的所需操作次數
假設我們有一個名為nums的數字列表。此列表的長度為偶數。現在考慮一個操作，我們選擇nums中的任何數字，並將其更新為[1和nums的最大值]範圍內的值。我們必須找到所需此類操作的最小數量，以便對於每個i，nums[i] + nums[n-1-i]等於相同的數字。
因此，如果輸入類似於nums = [8,6,2,5,9,2]，則輸出將為2，因為如果我們將nums[2]中的第一個2更改為5，並將nums[4]中的9更改為4，則元素將為[8,6,5,5,4,2]，則每個i的nums[i] + nums[n-1-i]將為(8+2) = (6+4) = (5+5) = 10。
為了解決這個問題，我們將遵循以下步驟：
- N := nums的大小
- mx := nums的最大值
- events := 一個新的列表
- idx := 0
- 當 idx < floor(N / 2) 時，執行：
- a := nums[idx]
- b := nums[N - idx - 1]
- 在events的末尾插入一對(min(a + 1, b + 1), 1)
- 在events的末尾插入一對(a + b, 1)
- 在events的末尾插入一對(a + b + 1, -1)
- 在events的末尾插入一對(max(a + mx, b + mx + 1), -1)
- idx := idx + 1
- 對列表events進行排序
- current := 0
- mx_same := 0
- 對於events中的每一對(event, delta)，執行：
- current := current + delta
- mx_same := max(current, mx_same)
- 返回 N - mx_same
示例
讓我們看看下面的實現，以便更好地理解：
def solve(nums): N = len(nums) mx = max(nums) events = [] idx = 0 while idx < N // 2: a = nums[idx] b = nums[N - idx - 1] events.append((min(a + 1, b + 1), 1)) events.append((a + b, 1)) events.append((a + b + 1, -1)) events.append((max(a + mx, b + mx) + 1, -1)) idx += 1 events.sort() current = 0 mx_same = 0 for event, delta in events: current += delta mx_same = max(current, mx_same) return N - mx_same nums = [8,6,2,5,9,2] print(solve(nums))
輸入
[6, 8, 5, 2, 3]
輸出
2
更新於：2021年10月18日
61 次瀏覽
廣告