通過添加元素

我在測試過這個問題就來了，減少陣列。通過添加元素

給定一個陣列，所述陣列減少以最小的成本的單個元素。爲了減少，從數組中刪除兩個元素，添加這兩個數字並將總和保留在數組中。每個操作的成本是該步驟中刪除的元素的總和。

實施例，讓陣列A = [1,2,3]

然後，我們可以除去圖1和2中，添加它們兩者，並保持之和回陣列。此步驟的成本將是（1 + 2）= 3

所以A = [3,3]，成本= 3

在第二步驟中，我們可以刪除從數組兩個元件和保持的總和重新排列。此步驟的成本將是3 + 3 = 6。

所以，A = [6]，成本= 6

所以總成本原來是9（6 + 3）。

我試圖排序陣列，以及從降低增加添加元素，但如果有重複的元素失敗。我的算法

sort(Array) 
cost = 0 
for(i=0; i<Array.length - 1; i++) { 
    Array[i+1] = Array[i] + Array[i+1] 
    cost = cost + Array[i+1] 
}

上述算法的

僞代碼不能正常工作。我想出了一個可能會失敗的例子。根據上述算法，如果Array = [5,5,5,5]，則Cost = 45。

但是，如果我們總結前兩個元素和最後兩個元素，然後求和其餘兩個元素，那麼總成本結果是40.（第一步，成本= 10 * 2，並在下一步另外20）

這可能是一個高效的算法呢？

來源

2016-12-06 AnkitAti

我認爲總是添加兩個最小的元素應該工作。你在做這個嗎？請顯示您正在使用的確切算法。當你將數字加回到數組中時，你把它放在前面，後面還是它所屬的位置w.r.t.排序？ –

我編輯了這個問題。我將這個總和保存回前面的數組中（用總和替換其中一個元素）。我認爲把這筆錢保存在適當的地方w.r.t.排序會花費一點時間，因爲我需要在每次更換後執行此操作。 – AnkitAti

也許你應該把這些元素放在堆或二叉搜索樹中？然後每次只花費O（logn）檢索兩個最小的元素。 –

你在正確的軌道與排序陣列和第一求和最低元素上。問題是：這兩個最低元素的總和可能比它們之後的下一個元素大，所以你不能把它放在前面。但它也可能比最後一個元素小，所以你也不能把它放在後面。你必須把它歸入它所屬的地方w.r.t.分揀。

例子：如果你的列表是[1, 1, 3, 3]，然後1+1應該被擺在了面前，即[2, 3, 3]，但如果我們有[2, 2, 3, 3]，然後總和2+2必須被放置在背部[3, 3, 4]，併爲[2, 2, 3, 5]是必須置於中間位置，即[3, 4, 5]。

一個簡單的方法來做到這一點是使用heap結構。這些語言在大多數語言中都可用，並提供了獲取和刪除最小元素以及將元素插入到正確位置的方法。下面是在Python的例子：

import heapq 
def reduce_sum(lst): 
    heapq.heapify(lst) 
    s = 0 
    while len(lst) > 1: 
     first = heapq.heappop(lst) 
     second = heapq.heappop(lst) 
     s += first + second 
     heapq.heappush(lst, first + second) 
    return s 

reduce_sum([1,2,3])  # 9 
reduce_sum([5, 5, 5, 5]) # 40

如果你不能使用堆，您仍然可以遍歷數組找到把總結元素，或者使用二進制搜索這樣做更快的正確的地方。

來源

2016-12-06 10:29:26

謝謝。我完全錯過了我可能最終在第一次添加之後添加更大的元素。 – AnkitAti

您的數組將永遠縮減爲其所有元素的sum。該還原"cost「可以雖然有所不同。最小可以通過添加當前存在的陣列中的兩個最低要素來實現。

最小堆可用於非常有效地解決這個問題。下面是在Java的例子。

public int[] sumAndCost(Integer[] arr) { 
     PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(Arrays.asList(arr)); 
     int sum = priorityQueue.poll(); 
     int cost = 0; 
     while (!priorityQueue.isEmpty()) { 
      int currentElement = priorityQueue.poll(); 
      if (currentElement < sum) { 
       priorityQueue.add(sum); 
       sum = currentElement; 
      } else { 
       sum += currentElement; 
       cost += sum; 
       continue; 
      } 

      sum += priorityQueue.poll(); 
      cost += sum; 
     } 

     return new int[] {sum, cost}; 
    }

它返回總和及任何給定陣列的成本。

條件語句可以看出有點uncessary但有些提高了我們的運行時間。

來源

2016-12-06 10:42:17 Default71721

通過添加元素

回答

相關問題