2017-06-06 47 views
6

तो मैं इस प्रोग्रामिंग समस्या को हल करने की कोशिश कर रहा था।सुबारै प्रश्न

संख्याओं और कुछ प्रश्नों की एक श्रृंखला को देखते हुए। प्रत्येक क्वेरी आपको तीन नंबर ए, बी, सी देता है और आपको इंडेक्स से सभी तत्वों के सूचकांक बी (दोनों शामिल) के उत्तर देने के लिए कहता है जो सी से कम या उसके बराबर हैं।

उदाहरण के लिए

:

को देखते हुए सरणी: {} 2,4,6,1,5,1,6,4,5,4

3 प्रश्नों का जवाब दिया जा करने के लिए कर रहे हैं:

2 से 4 4 -> ans = 5 यानी {4 + 1}

1 5 3 -> ans = 3 यानी {2 + 1}

4 5 1 -> ans = 1

प्रत्येक सरणी में मान 10^5 से कम है, सरणी की लंबाई और प्रश्नों की संख्या 10^5

यहां मैंने क्या किया है मैंने प्रश्नों को हल करने के लिए मो के एल्गोरिदम (स्क्वायर रूट अपघटन) का उपयोग किया है, और बनाया है 1-10^5 से सभी मानों से कम तत्वों के संचयी योग को संग्रहीत करने के लिए एक बाइनरी अनुक्रमित पेड़, और प्रश्नों से प्रश्नों के लिए एक अद्यतन को अद्यतन किया। इस एल्गोरिदम के साथ मेरे समाधान की समग्र जटिलता ओ (क्यू * वर्ग (एन) * लॉग (एन) है लेकिन यह पर्याप्त तेज़ नहीं है। मैं एक बेहतर एल्गोरिदम की तलाश में था। मुझे लगता है कि प्रश्नों का वर्ग-रूट अपघटन काम नहीं करेगा। क्या इस समस्या को हल करने के लिए कोई बेहतर एल्गोरिदम है?

मैं सोच रहा था कि क्या कुछ डेटा-संरचना इस समस्या को हल कर सकती है जिसे मैं अनजान हूं?

+0

आपका मतलब है "ए", "बी", "सी" इंडेक्स हैं? और क्या आप शून्य-आधारित अनुक्रमण का उपयोग कर रहे हैं? – Bahrom

+0

@ बाह्रोम ए और बी '1' आधारित सूचकांक हैं, सी एक संख्या है। – ash

उत्तर

2

आप इसे दूसरी तरफ विघटित कर सकते हैं। अर्थात्, आधा सरणी का पेड़ बनाएं (यह है (एन लॉग एन) स्थान)। प्रत्येक subarray सॉर्ट करें और इसके लिए एक संचयी योग सरणी बनाएँ। अब आपके प्रश्नों (लॉग n) प्रत्येक (n subarrays और एक अन्य लॉग n पहचान करने के लिए प्रत्येक subarray में संचयी योग को खोजने के लिए लॉग इन करें) कर रहे हैं।

उदाहरण के लिए, यदि आपके मूल सरणी

  5,10,2,7,16,4,8,9 

आप पहली बार इस पेड़

  5,10,2,7,16,4,8,9 
      /  \ 
     5,10,2,7   16,4,8,9 
    / \   / \ 
    5,10  2,7  16,4  8,9 
    /\ /\ /\  /\ 
    5 10 2 7 16 4  8 9 

निर्माण फिर उन सभी को

  2,4,5,7,8,9,10,16 
      /  \ 
     2,5,7,10   4,8,9,16 
    / \   / \ 
    5,10  2,7  4,16  8,9 
    /\ /\ /\  /\ 
    5 10 2 7 16 4  8 9 

सॉर्ट अब अगर आप क्वेरी कहना जवाब देने के लिए करना चाहते हैं (1,6,8) (सूचकांक 0-आधारित हैं) आप द्विआधारी उपनिवेश (1) (2,3) (4,5) (6) में (1,6) अंतराल को विघटित करते हैं (वहां) 2 से अधिक लॉग n उनमें से) प्रत्येक के लिए अलग से जवाब प्राप्त करें (0 (1) = {10}, 9 के लिए (2,3) = {2,7}, 4 के लिए (4,5) = {16,4}, 8 (6) = {8}) के लिए और उन्हें योग करें।

प्रारंभिक पेड़ इमारत में (n लॉग n) किया जा सकता है अगर आप जोड़े (मूल्य सूचकांक) एक बार को सॉर्ट और फिर बस क्रमबद्ध सरणी लॉग n बार (एक बार हर एक पेड़ के स्तर के लिए) और प्रतिलिपि के ऊपर से गुजरती उनके संबंधित नोड्स के लिए मूल्य।

+0

कार्यान्वयन के संबंध में, आप पेड़ पर एक पुनरावर्ती कार्य को परिभाषित कर सकते हैं जो (1) अंतराल में पूरी तरह निहित होने पर केवल वर्तमान नोड का योग देता है, (2) या तो बाएं या दाएं बच्चे के फ़ंक्शन का परिणाम देता है योग अगर अंतराल केवल बाएं या दाएं तरफ है, (3) बाएं और दाएं बच्चों दोनों पर फ़ंक्शन कॉल का योग देता है यदि अंतराल दोनों तरफ होता है, यानी बीच में चला जाता है। शुरुआत में पूरी तरह से अंतराल को विभाजित करने की कोशिश करने से यह आसान लगता है। ऐसा लगता है कि प्रति क्वेरी केवल ओ (लॉग एन) की तरह है। – Dukeling

+0

क्या आप विस्तार से बता सकते हैं कि आप सी के बराबर या उसके बराबर तत्वों की वास्तविक राशि कैसे प्राप्त करते हैं (ओ (लॉग एन) में)? ऐसा करने का एक तरीका प्रत्येक नोड के लिए संचयी योग को संग्रहीत करना होगा, फिर लागू नोड को खोजने के लिए उस नोड के भीतर एक बाइनरी खोज करने के लिए। – Dukeling

+0

@ हुकिंग हां यह वही है जो मुझे दिमाग में था –