我在課堂上得到了一個練習，需要以下內容：由 N 個整數組成的數組 v 是循環排序的，如果該數組是有序的，或者 和v[N‐1] ≤ v[0]，?k例如0<k<N。?i≠k v[i] ≤ v[i+1]例子：給定一個包含多達 10 個正項的循環排序數組，計算正值的總和。對于最后一個例子，答案是 27。我被要求在java中使用分而治之的方案來實現它，因為最壞情況下的復雜性是O(Log N)，即 N 是數組大小。到目前為止，我嘗試旋轉一個值，直到找到一個正值，然后知道其他正值是相鄰的，就可以以 O(1) 的復雜度對 10 個正值的最大值進行求和。我想過進行二分搜索來實現 O(Log N) 復雜度，但這不遵循分而治之的模式。我可以輕松地通過 O(N) 復雜度來實現它，如下所示：public static int addPositives(int[] vector){ return addPositives(vector,0,vector.length-1}public static int addPositives(int[] vector, int i0, int iN){ int k = (i0+iN)/2; if (iN-i0 > 1){ return addPositives(vector,i0,k) + addPositives(vector,k+1,iN); }else{ int temp = 0; for (int i = i0; i <= iN; i++) { if (vector[i]>0) temp+=vector[i]; } return temp; }}然而，試圖達到 O(Log N) 卻毫無進展，我該如何實現呢？
2 回答
月關寶盒
TA貢獻1772條經驗 獲得超5個贊
如果您修剪遞歸的不相關分支，則可以改進分而治之的實現以滿足所需的運行時間。
將當前數組分為兩個子數組后，比較每個子數組的第一個和最后一個元素。如果兩者都是負數并且第一個小于最后一個，您可以確定該子數組中的所有元素都是負數，并且您不必對其進行遞歸調用（因為您知道它將為 0 貢獻）總金額）。
如果子數組中的所有元素都是正數，您也可以停止遞歸（也可以通過比較子數組的第一個和最后一個元素來驗證） - 在這種情況下，您必須將該子數組的所有元素相加-array，所以沒有必要繼續遞歸。
交互式愛情
TA貢獻1712條經驗 獲得超3個贊
我對 O(Log N) 的建議是直接比較以滿足兩個標準中的第二個：最后一項小于第一項。 return vector[0] >= vector[iN-1]
如果你想要更復雜的東西，我忘記了算法名稱，但你可以在中間點獲取數組，并從那里進行兩次有序搜索：從中間到開始，然后從中間到結束
添加回答
舉報
0/150
提交
取消