Directi面試中被問到的問題取一個輸入數組，比如 A 并打印 x 的最大值，其中x = |(A[i] – A[j]) + (i – j)|Constraints:Max array size: 20000Time limit: 0.1s時間限制是這個問題的主要因素。這是設置者針對此問題的解決方案。'''THE BRUTE FORCE APPROACHdef maximum(arr): res=0 n=len(arr) for i in range (n): for j in range(n): res=max(res,abs(arr[i]-arr[j])+abs(i-j)) return res '''import sysdef maximum(arr): max1=max2=-sys.maxsize-1 min1=min2=sys.maxsize ans=0 n=len(arr) for i in range(n): max1=max(max1,arr[i]+i) max2=max(max2,arr[i]-i) min1=min(min1,arr[i]+i) min2=min(min2,arr[i]-i) ans=max(ans,max2-min2) ans=max(ans,max1-min1) return ans 但我嘗試使用解決問題sortdef maximum(array): n=len(array) array.sort() return (array[n-1]-array[0]) + (n-1) if __name__=="__main__": n=int(input()) array= list(map(int,input("\nEnter the numbers : ").strip().split()))[:n] print(maximum(array))我的方法正確嗎？優化了嗎？提前致謝。
2 回答
慕少森
TA貢獻2019條經驗 獲得超9個贊
建議的首先排序和獲取元素的答案是不正確的。以反例為例：[2,1,3]
此問題的解決方案應產生 3：
(3-1) + (2-1)或(3-2) + (2-0)但是，建議的解決方案將產生 4：
(3-1) + (2-0)
一個可能的（線性時間）解決方案：
讓我們從一些代數開始，暫時去掉絕對值。
(A[i] – A[j]) + (i – j) = (A[i] + i) - (A[j] + j)
我們正在尋找最大價值，所以
我們想最小化的價值
(A[j] + j)我們想要最大化 的價值
(A[i] + i)。請注意，它們彼此完全獨立。
您可以找到兩個整數，一個使 最大化(A[i] + i)，另一個使 最小化(A[j] + j)。找到這樣的 2 個數字可以簡單地在線性傳遞中完成。
以相反的方式重復（當(A[i] – A[j]) + (i – j)為負時）：
找到最小化的 i
(A[i] + i)很好
j，最大化(A[j] + j)。
兩者都在線性時間內完成，產生O(n)解決方案
呼喚遠方
TA貢獻1856條經驗 獲得超11個贊
排序會擾亂原始數組，并且元素在各自索引處的映射會丟失。所以從邏輯上講，排序會導致錯誤的答案。
例如，正如@amit 在他的評論中正確描述的那樣：
A = [2, 1, 3]
正確答案 = 3
建議的解決方案答案 = 4
添加回答
舉報
0/150
提交
取消