以最小的空間複雜度查找數組中最大整數的總和

我是編程新手，嘗試通過探索學習。我正在尋找一個解決方案來找到數組中具有最佳空間複雜度的重複整數的最大時間總和。假設我們有[1，2，3，3]結果應該是6，並且空間複雜度最小，比如O（n）。以最小的空間複雜度查找數組中最大整數的總和

我想出了一個解決方案，但不確定複雜性。需要一些幫助來了解下面提到的代碼是否具有最小的複雜性，或者它可能會更好（絕對是！）。對不起，如果我犯了錯誤，並提前致謝。

public static int maxDuplicateSumSpaceBased(int[] a) 
{ 
    int maxRepCount = 1, tempCount; 
    int maxRepNum = a[0]; 
    int temp = 0; 
    for (int i = 0; i < (a.length - 1); i++) 
    { 
    temp = a[i]; 
    tempCount = 0; 
    for (int j = 1; j < a.length; j++) 
    { 
     if (temp == a[j]) 
     tempCount++; 
    } 
    if (tempCount > maxRepCount) 
    { 
     maxRepNum = temp; 
     maxRepCount = tempCount; 
    } 
    } 
    return maxRepNum * maxRepCount; 
}

來源

2015-11-08 new guy

對不起，我的意思是程序應該儘可能低的內存消耗。希望它清楚，謝謝 –

從空間複雜性的角度來看，你的算法是很好的，因爲它只使用一些原始變量。當O（n）可能時，其時間複雜度爲O（n^2）。 –

謝謝，是的，我瞭解通過消除雙循環來提高時間複雜度，這裏我更關心空間複雜性。如果您可以指導，那麼上述計劃的空間複雜程度如何？ –

實際上，輸入的空間通常不會在O符號計數，從而程序具有的O的空間複雜性（6）= O（C）= O（1）。 c是一個常數。事實上，你總是使用6個變量。如果使用的空間量取決於輸入，但情況不同，但不是這種情況，因爲不管輸入的長度如何，您總是使用6個變量。

如果您想將輸入計爲佔用空間（有時會完成），假設n是輸入的長度，則空間複雜度爲O（6 + n）= O（n）。

你不可能做得更好，因爲你可以很容易地證明：你不能有比輸入少的內存佔用（或者你必須記住所有的輸入）。由於輸入是唯一不是常數的東西，所以使用的最大空間是存儲n的輸入所需的空間。

來源

2015-11-08 13:45:39 JoulinRouge

空間複雜度您的解決方案是O(1)。你不能比這更好。

解決方案的時間複雜度爲O(N^2)。您可以在幾個方面提高對：

如果你可以修改a，那麼你就可以對它進行排序{時間O(NlogN)，空間O(1)}然後找到/數最頻繁的值{O(N)，O(1)}。整體複雜性是{O(NlogN),O(1)}。
如果您不能修改a，那麼將其複製{O(N)/O(N)}，然後按上述步驟繼續。總的複雜性是{O(NlogN),O(N)}。
如果數字的範圍（M）小於數字的數量，那麼您可以使用水桶排序。總的複雜性是{O(N)，O(M)}。
使用HashMap可以獲得更好的整體時間複雜度。其總體複雜性將爲{O(N)，平均值爲O(N)} ......具有顯着較大的比例常數。（不幸的是，最壞情況下的時間複雜度將是O(NlogN)或O(N^2)取決於哈希表的實現。當所有的按鍵衝突就發生了。這是不可能的Integer鍵和HashMap，但可能Long鍵。）

^{1 - 我指的是空間另外到輸入數組佔用的空間。顯然，用於輸入數組的空間不能被優化。這是一個給定的。}

來源

2015-11-08 13:51:17

輸入是一個整數的數組，有一些努力可以設法解決O（n）中的問題，而不用修改一個正確編輯的整數排序 – JoulinRouge

@JoulinRouge - 真的嗎？請解釋（在一個答案中） –

不，我寫了「有些努力」:) – JoulinRouge

我已經理解你的問題了。現在可以有一個解決方案有n個整數和所有整數k [1-n]。然後找到maxrepeatnumber需要O（n）時間。

public static int maxDuplicateSumSpaceBased(int[] a) 
{ 
    int maxRepCount = 1, tempCount; 
    int k=a.length(); 
    for (int i = 0; i <k; i++) 
    { 
     a[a[i]%k]+=k; 
    } 
    int maxRepnumber=0,temp=a[0]; 
    for (int j = 1; j < k; j++) 
    { 
     if (temp < a[j]) 
     { 
      temp=a[j]; 
      maxRepnumber=j; 
     } 
    } 

    } 
    return maxRepNum; 
} 

Then you sum all that number and it take O(n)and O(1) space.

來源

2015-11-08 14:35:28

以最小的空間複雜度查找數組中最大整數的總和

回答

相關問題