尋找具有相等數量的0和1的

最大子陣列所以，我有僅包含0和1的陣列。我必須找出包含相同數量的0和1的最大子數組。一個可以是一種天真的方法，其複雜性如下：O(n^2)其中我將外部循環中的每個元素都計算在內部循環中，並計算內部循環中可能的子數組，並且如果發現則繼續更新最大大小。是否還有其他更好的方法（比如O（n））可以使用？謝謝！尋找具有相等數量的0和1的

Input: arr[] = {1, 0, 1, 1, 1, 0, 0} 
Output: 1 to 6 (Starting and Ending indexes of output subarray)

來源

2015-07-03 John Lui

下面是一個爲O（n） - 時間，爲O（n）空間算法。我不確定它是否是最佳選擇，但是它打敗了二次時間。

的基本思路如下。假設你從數組左邊掃描到右邊的記錄，在每一步中，1的數量和0的數量之間的差值。如果你在每一個步驟寫這些值了，你會得到這樣的事情：

1, 0, 1, 0, 0, 0, 0 
0, 1, 0, 1, 0, -1, -2, -3

如果你有相同數量的0和1，隨後的0和1的在淨差額子陣列子數組的開始等於子數組後的淨數。因此，試圖在輔助陣列中找到兩個相等且儘可能相距很遠的相等值時，可以重新構造這個問題。

的好消息是，在陣列中的每個條目是-n和+ N之間，這樣就可以使一個2N + 1個元素表，並存儲在它的第一次也是最後一次出現的每個數字指標。從那裏，很容易找到最長的範圍。總的來說，這需要O（n）空間，並且可以在O（n）時間內填充和搜索所有內容。

希望這會有所幫助！

來源

2015-07-03 07:58:39 templatetypedef

對，這會做。對。偉大的想法。 :) –

什麼關於以下的序列： '0 0 0 0 1 0 1 0 0 0' –

這將使陣列0，-1，-2，-3，-4，-3，-4， - 3，-4，-5，-6。無論是由-3分隔的範圍還是由-4分隔的範圍都會給你你正在尋找的東西。雖然也許我錯過了什麼？ – templatetypedef

首先將您的零轉換爲-1。然後你正在尋找一個零和的最大子陣列。此算法被描述here

來源

2015-07-03 07:56:44 vib

但是，然後，它會發現所有的和數爲0的子數組，並且最大長度爲1。發現一個子陣列本身具有O（n）的時間複雜度，然後我會這樣做（在最壞的情況下，我猜測是n次），使它再次成爲O（n^2）。 –

如果你查看我給你的鏈接，你會看到那裏有一個O（n）的答案。但另一個答案是更具體的這個問題，更好的... – vib

鏈接中的算法找到第一個子數組，而不是最長的子數組。另外，它不認爲數據的二進制性質。 –

public int equalNumber(int arr[]){ 

    int sum[] = new int[arr.length]; 
    sum[0] = arr[0] == 0? -1 : 1; 
    for(int i=1; i < sum.length; i++){ 
     sum[i] = sum[i-1] + (arr[i] == 0? -1 : 1); 
    } 

    Map<Integer,Integer> pos = new HashMap<Integer,Integer>(); 
    int maxLen = 0; 
    int i = 0; 
    for(int s : sum){ 
     if(s == 0){ 
      maxLen = Math.max(maxLen, i+1); 
     } 
     if(pos.containsKey(s)){ 
      maxLen = Math.max(maxLen, i-pos.get(s)); 
     }else{ 
      pos.put(s, i); 
     } 
     i++; 
    } 
    return maxLen; 
}

來源

2016-04-15 16:20:52 SWAR0714

如果通過一些關於它如何回答問題和運行復雜性的討論進行編輯，可以進行改進。 – paisanco

上述要求，如果任何人有任何更好的方法，我有這一個，所以我共享它.. – SWAR0714

從https://discuss.leetcode.com/topic/25465/longest-continous-zero-sum-subarray/6複製＃ – EmptyData

尋找具有相等數量的0和1的

回答

相關問題