subarrays की एक सरणी का योग खोजें

Question

यह 2017 Google एपीएसी से एक प्रश्न है। Problem D: Sum of Sum

ऐलिस एन धनात्मक पूर्णांक की एक सरणी, 1 से एन वह प्रपत्र के कई प्रश्नों के साथ बॉब चुनौती दी करने के लिए अनुक्रमित के साथ उसके दोस्त बॉब प्रस्तुत "एक के इंडेक्स के बीच संख्याओं का योग क्या है?" लेकिन बॉब समस्या को आसानी से हल करने में सक्षम था। एलिस ने अपनी सरणी ली और उसे सभी एन * (एन + 1)/2 गैर खाली खाली उपरोक्त पाया। उसे प्रत्येक उपराष्ट्रय का योग मिला, और फिर 1 से एन * (एन + 1)/2 से अनुक्रमित एक नई सरणी बनाने के लिए उन मानों को (nondecreasing आदेश में) क्रमबद्ध किया। उदाहरण के लिए, प्रारंभिक सरणी [2, 3, 2] के लिए, ऐलिस उपन्यास [2], [3], [2], [2, 3], [3, 2], और [2, 3, 2] (ध्यान दें कि [2, 2], उदाहरण के लिए, एक उपन्यास नहीं है)। फिर वह रकम लेती है - 2, 3, 2, 5, 5, 7 - और उन्हें [2, 2, 3, 5, 5, 7] की एक नई सरणी प्राप्त करने के लिए क्रमबद्ध करें .इसिस ने प्रारंभिक दिया है फॉर्म के क्यू प्रश्नों के साथ बॉब के लिए सरणी "इंडेक्स ली से री, समेकित, नई सरणी में संख्याओं का योग क्या है?" अब बॉब परेशानी में है! क्या आप उसकी मदद कर सकते हैं?

सीधे डेटा समाधान बड़े डेटा सेट के लिए सी ++ में भी अक्षम है। क्या इसे हल करने का एक और अधिक प्रभावी तरीका है?

multiset<int> sums; 
    long long int temp = 0; 
    for (long long int len = 1; len <= n; ++len) 
    { 
     for (int start = 0; start+len <= n; ++start) 
     { 
      temp = 0; 
      for (int i = 0; i < len; ++i) 
      { 
       temp += arr[start + i]; //arr stores the original array of n digits 
      } 
      sums.insert(temp); 
     } 
    } 

पी.एस:

वर्तमान में मैं अंतिम सरणी के निर्माण के लिए पाश के लिए इस के माध्यम से जा रहा हूँ है मेरे वर्तमान कार्यान्वयन O (n^5)? मेरी गलती, मैं देख सकता हूं कि यह ओ (एन^3) अब कैसे है। धन्यवाद संपादित करें: उत्तर अब तक सहायक रहे हैं लेकिन एन = 200000 वस्तुओं से जुड़े बड़े डेटासेट के साथ, ऐसा लगता है कि उपरोक्त की पूरी सरणी की गणना करने वाला कोई भी समाधान बहुत महंगा है। सभी सबमिट किए गए समाधान subarrays की पूरी सरणी की गणना करने के लिए प्रकट नहीं होते हैं

Answer 1

एक छोटे से खोज मैं इस पाया है कर, मुझे आशा है कि यह उपयोगी होगा

https://www.quora.com/How-can-problem-D-Sums-of-sums-from-Round-E-of-the-Google-APAC-Test-2016-be-solved-for-the-large-dataset

Answer 2

टिप्पणियों में उल्लेख किया गया है, आपका समाधान ओ (एन^3) है, जिसे ओ (एन^2) बार ओ (एन) योग के रूप में गणना की जाती है और मल्टीसेट में एक सम्मिलन (जिसे आप ओ (एन) की तुलना में अनदेखा कर सकते हैं, इस उत्तर के नीचे देखें)।

लेकिन अपने दो पहले छोरों स्वैप, आप ठीक उसी एन * कर रहे हैं (N + 1)/2 रकम और सम्मिलन:

for (int start = 0; start < n; ++start) 
{ 
    for (long long int len = 1; start + len <= n; ++len) 
    { 
     temp = 0; 
     for (int i = 0; i < len; ++i) 
     { 
      temp += arr[start + i]; //arr stores the original array of n digits 
     } 
     sums.insert(temp); 
    } 
} 

अब अगर आप देखो

अपने temp पर योग यह आप स्पष्ट लगता अनावश्यक काम कर रहे हैं। start + 1 से start + 3, आदि प्रत्येक नए len के लिए करने के लिए start + 1 से start + 2 को start + 1 से start + 1 का योग है, तो, फिर, योग आप कंप्यूटिंग रहे len के पिछले मूल्य के लिए एक, के साथ साथ एक आइटम है।

for (int start = 0; start < n; ++start) 
{ 
    temp = 0; 
    for (long long int len = 1; start + len <= n; ++len) 
    { 
     temp += arr[start + len]; //arr stores the original array of n digits 
     sums.insert(temp); 
    } 
} 

तो एन * (N + 1)/2 में आप मूल्यों का वह समूह उत्पन्न: इसलिए आप इस भीतरी पाश निकाल सकते हैं। बेशक, एक मल्टीसेट का उपयोग करके आप डेटा सॉर्टिंग को छुपाते हैं, लेकिन सामान्य लागत में सम्मिलन log(sums.size()) है।

आकार एस के एक सेट को सॉर्ट करने के बाद अलग से छंटनी, एस * लॉग (एस) लेना चाहिए, N*(N+1)/2 * log (N*(N+1)/2) खर्च होगा जो कि (0) N*(N+1) * log((N+1)/sqrt(2)) से कम है।

ध्यान दें कि चूंकि आपके पास सकारात्मक पूर्णांक हैं, इसलिए len प्रत्येक सेट जो आप आंतरिक लूप के साथ उत्पन्न करते हैं, पहले ही सॉर्ट किया गया है, इसलिए हो सकता है कि आप उन्हें सॉर्टिंग को गति देने के लिए कुछ स्मार्ट करने के लिए उपयोग कर सकें।जो भी है क्या मल्टीसेट करता according to cplusplus.com:

एन तत्वों डाला रहे हैं, तो Nlog (आकार + N) सामान्य रूप में, लेकिन आकार में रैखिक + N तत्वों को पहले ही द्वारा इस्तेमाल किया एक ही आदेश कसौटी के अनुसार हल कर रहे हैं, तो कंटेनर।

Answer 3

सबसे संक्षिप्त और कारगर तरीका मैं के बारे में सोच सकते हैं यह है:

std::vector<int> in{ 2, 3, 2 }; 
std::vector<int> out(in.size()*(in.size()+1)/2); 

auto out_it = out.begin(); 
for (size_t i = 0; i < in.size() ; ++i) { 
    out_it=std::partial_sum(in.begin()+i, in.end(), out_it); 
} 
std::sort(out.begin(), out.end()); 

जटिलता विचार बगल में (यह समाधान है - मेरा मानना ​​है कि - O (n^2 * लॉग (एन)) आप के रूप में ओ (एन^2) प्रविष्टियों के साथ एक सरणी को सॉर्ट कर रहे हैं), आपको प्लेग की तरह गतिशील स्मृति आवंटन और पॉइंटर का पीछा करना चाहिए (जो दोनों std::multi_set का अंतर्निहित हिस्सा हैं)।