0 की संख्या के बराबर और 1 के

Question

के साथ सबसे बड़ा subarray ढूँढना तो, मैं केवल 0 और 1 के युक्त एक सरणी है। मुझे सबसे बड़ा सबराय पता होना चाहिए जिसमें बराबर संख्या 0 और 1 है। एक हो सकता है एक अनुभवहीन दृष्टिकोण O(n^2) जहाँ मैं बाहरी पाश में हर तत्व लेने के लिए और भीतरी पाश में संभव subarrays की गणना और अधिकतम आकार को अद्यतन करने के रखने के लिए, यदि पाया के रूप में जटिलता है। क्या कोई अन्य बेहतर दृष्टिकोण है (ओ (एन) जैसे कुछ) जिसका मैं उपयोग कर सकता हूं? धन्यवाद!

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

Answer 1

यहां एक ओ (एन) -टाइम, ओ (एन)-स्पेस एल्गोरिदम है। मुझे यकीन नहीं है कि यह इष्टतम है, लेकिन यह वर्गबद्ध समय धड़कता है।

मूल विचार इस प्रकार है। मान लीजिए कि आप प्रत्येक चरण में सरणी के बाएं से दाएं रिकॉर्डिंग तक स्कैन करते हैं, 1s की संख्या और 0 की संख्या के बीच का अंतर। आप प्रत्येक चरण में इन मूल्यों को लिखने, तो आप इस तरह कुछ मिल जाएगा:

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

आप 0s और 1s, की समान संख्या तो कम से 0s और 1s का शुद्ध अंतर के साथ एक उप सरणी है, तो subarray की शुरुआत subarray के बाद शुद्ध संख्या के बराबर होगी। इसलिए, इस समस्या को सहायक सरणी में दो समान मानों को खोजने की कोशिश के रूप में दोहराया जा सकता है जो बराबर और यथासंभव दूर हैं।

अच्छी खबर यह है कि सरणी में प्रत्येक प्रविष्टि -n और + n के बीच होती है, ताकि आप 2 एन + 1 तत्व तालिका बना सकें और इसमें प्रत्येक नंबर दिखाई देने वाले पहले और आखिरी बार के सूचकांक स्टोर कर सकें। वहां से, सबसे लंबी दूरी को ढूंढना आसान है। कुल मिलाकर, इसे ओ (एन) स्पेस की आवश्यकता होती है और ओ (एन) समय में सब कुछ पॉप्युलेट और खोजा जा सकता है।

आशा है कि इससे मदद मिलती है!

Answer 2

पहले अपने शून्य को -1 में परिवर्तित करें। फिर आप शून्य राशि के अधिकतम सबएरे की तलाश में हैं। इसके लिए एक एल्गोरिदम here

Answer 3

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; 
}