सरणी का सबसे छोटा सबसेट जिसका योग कुंजी

Question

से कम नहीं है, एक सरणी (गैर नकारात्मक पूर्णांक मानने दें) को देखते हुए हमें सबसे छोटी लंबाई सबसेट मिलना आवश्यक है जैसे कि तत्वों का योग K.K से कम नहीं है, एक और पूर्णांक प्रदान किया गया है इनपुट के रूप में।

क्या समय जटिलता ओ (एन) [एन ओ के बड़े] के साथ समाधान करना संभव है?

मेरी वर्तमान सोच निम्न पंक्तियों के साथ है: हम ओ (एन * लॉग एन) में सरणी को सॉर्ट कर सकते हैं और फिर सबसे बड़ी संख्या से शुरू किए गए क्रमबद्ध सरणी पर पुनरावृत्त कर सकते हैं और चल रहे योग तक चलने वाले योग को बनाए रख सकते हैं> = के।

हालांकि, यह ओ (एन * (लॉग एन + 1) का सबसे खराब मामला चलने का समय होगा)।

तो किसी को भी हे में (एन) समय ऐसा करने का विचारों को साझा कर सकता है, मैं वास्तव में सराहना करेंगे ..

नोट: subarray के तत्वों न इस संदर्भ में मूल सरणी का एक सन्निहित अनुक्रम होना जरूरी

Answer 1

के सबसे बड़ी संख्या - http://en.wikipedia.org/wiki/Selection_algorithm खोजने के लिए एक रैखिक समय एल्गोरिदम है। बेशक आप जो चाहते हैं वह कम से कम के लिए पर्याप्त संख्या है।

मानक चयन एल्गोरिदम में, आप एक यादृच्छिक पिवट लेते हैं और फिर देखते हैं कि इसके प्रत्येक किनारे पर कितनी संख्याएं गिरती हैं। फिर आप एक आधा स्वीकार या अस्वीकार करते हैं, और दूसरे छमाही पर काम करते रहते हैं। आपने प्रत्येक आधे में प्रत्येक संख्या को देखा है, बदले में - प्रत्येक पिवट चरण की लागत रैखिक है, लेकिन प्रत्येक चरण में मानी गई डेटा की मात्रा इतनी तेजी से कम हो जाती है कि कुल लागत अभी भी केवल रैखिक है।

एक पिवट चरण की लागत अभी भी केवल रैखिक होगी यदि आप पिवट के ऊपर सभी संख्याओं का योग लेते हैं। इसका उपयोग करके, यदि आप पहले से चुने गए किसी भी नंबर के साथ इन सभी नंबरों को स्वीकार करते हैं, तो आप काम कर सकते हैं, कम से कम के लिए जो संख्याएं जोड़ती हैं, उन्हें संग्रहित किया जाएगा। यदि ऐसा होता है, तो आप अन्य नंबरों को हटा सकते हैं और उपरोक्त संख्याओं का उपयोग कर सकते हैं अगले पास के लिए पिवट। यदि ऐसा नहीं होता है, तो आप पिवट के ऊपर सभी संख्याओं को स्वीकार कर सकते हैं, और अगले पास के लिए पिवट के नीचे की संख्या का उपयोग कर सकते हैं। चयन एल्गोरिदम के साथ, पिवट स्वयं और किसी भी संबंध आपको कुछ विशेष मामले और जल्दी सटीक उत्तर खोजने की संभावना देते हैं।

(इसलिए मुझे लगता है कि आप चयन एल्गोरिदम के संशोधित संस्करण का उपयोग करके इसे (यादृच्छिक) रैखिक समय में कर सकते हैं जिसमें आप पिवट के ऊपर कितनी संख्याएं हैं, इसके बजाय आप पिवट के ऊपर की संख्याओं के योग को देखते हैं।

Answer 2

यह गतिशील प्रोग्रामिंग के लिए एक समस्या प्रतीत होता है। जब आप अपनी सरणी बनाते हैं, तो आप प्रत्येक विशेष अनुक्रमणिका में संचयी योग युक्त एक और सरणी बनाते हैं। इसलिए उस सरणी में प्रत्येक i में 1..i से रकम है।

अब यह देखने के लिए कि सूचकांक p..q के लिए मानों का योग SUM(q) - SUM(p-1) है (विशेष मामला है कि SUM(0)0 है) के साथ आसान है। जाहिर है, मैं यहां 1-आधारित इंडेक्स का उपयोग कर रहा हूं ... यह ऑपरेशन ओ (1) है, इसलिए अब आपको सबसे अच्छा खोजने के लिए ओ (एन) एल्गोरिदम की आवश्यकता है।

एक आसान समाधान p और q का ट्रैक रखना और सरणी के माध्यम से इन्हें चलाना है। शुरू करने के लिए आप q के साथ विस्तार करें। फिर आप p अनुबंध करते हैं और बार-बार q का विस्तार करते हैं, जैसे आपके सरणी के माध्यम से एक कैटरपिलर क्रॉलिंग।

q का विस्तार करने के लिए:

p <- 1 
q <- 1 

while SUM(q) - SUM(p-1) < K 
    q <- q + 1 
end while 

अब q स्थान है जहाँ subarray राशि सिर्फ पार कर गया है पर है (या के बराबर है) K। उपराय की लंबाई q - p + 1 है।

q लूप के बाद आप जांच करते हैं कि उपर्युक्त लंबाई आपके वर्तमान सर्वोत्तम से कम है या नहीं। फिर आप p को एक चरण से आगे बढ़ाते हैं (ताकि आप गलती से इष्टतम समाधान पर न छोड़ें) और फिर जाएं।

आपको वास्तव में SUM सरणी बनाने की ज़रूरत नहीं है ... आप केवल उपरोक्त राशि बना सकते हैं जैसे आप जाते हैं ... आपको पहले 'वास्तविक' p का उपयोग करने के लिए वापस जाना होगा ।

subsum <- VAL(1) 
p <- 1 
q <- 1 

while q <= N 
    -- Expand 
    while q < N and subsum < K 
     q <- q + 1 
     subsum <- subsum + VAL(q) 
    end while 

    -- Check the length against our current best 
    len <- q - p + 1 
    if len < bestlen 
     ... 
    end if 

    -- Contract 
    subsum <- subsum - VAL(p) 
    p <- p + 1 
end while 

नोट्स:

j_random_hacker ने कहा: यह समझाने के लिए मदद मिलेगी सभी हे के बजाय वास्तव में क्यों यह सिर्फ हे (एन) की जांच अलग subarrays कि इस एल्गोरिथ्म की जांच करता है को स्वीकार्य है (एन^2) संभव अलग subarrays

गतिशील प्रोग्रामिंग दर्शन है:

1. समाधान पथ का पालन न करें जो एक गैर-इष्टतम परिणाम का कारण बनेंगे; और
2. नए समाधान की गणना करने के लिए पिछले समाधानों के ज्ञान का उपयोग करें।

इस मामले में एकमात्र समाधान उम्मीदवार (कुछ (p,q) ऐसे p <= q कि) तत्वों का संक्षेप द्वारा गणना की जाती है। चूंकि वे तत्व सकारात्मक पूर्णांक हैं, हम जानते हैं कि किसी भी समाधान उम्मीदवार (p,q) के लिए, समाधान उम्मीदवार (p,q+1) बड़ा होगा।

और इसलिए हम जानते हैं कि (p,q) एक न्यूनतम समाधान है तो (p,q+1) नहीं है। जैसे ही हमारे पास उम्मीदवार होता है, हम अपनी खोज समाप्त करते हैं, और परीक्षण करते हैं कि क्या उम्मीदवार अब तक किसी भी व्यक्ति से बेहतर है या नहीं। इसका मतलब है प्रत्येक p के लिए, हमें केवल एक उम्मीदवार का परीक्षण करने की आवश्यकता है। इससे p और q दोनों ही बढ़ रहे हैं, और इस प्रकार खोज रैखिक है।

इसका दूसरा भाग (पिछले समाधानों का उपयोग करके) sum(p,q+1) = sum(p,q) + X(q+1) और इसी प्रकार sum(p+1,q) = sum(p,q) - X(p) को पहचानने से आता है। इसलिए, हमें प्रत्येक चरण में p और q के बीच सभी तत्वों को योग करने की आवश्यकता नहीं है। जब भी हम खोज बिंदुओं में से किसी एक को अग्रिम करते हैं तो हमें केवल एक मूल्य जोड़ना या घटाना होगा।

आशा है कि मदद करता है।

Answer 3

यहाँ एक समाधान काफी तेजी से किया जाना चाहिए है। मैं यह लगभग रैखिक है अनुमान लगा रहा हूँ।

def solve(A, k): 
    assert sum(A) >= k 
    max_ = max(A) 
    min_ = min(A) 
    n = len(A) 
    if sum(A) - min_ < k: 
     return A 
    bucket_size = (max_ - min_)/n + 1 
    buckets = [] 
    for i in range(n): 
     buckets.append([]) 
    for item in A: 
     bucket = (item - min_)/bucket_size 
     buckets[bucket].append(item) 

    solution = [] 

    while True: 
     bucket = buckets.pop() #the last bucket 
     sum_ = sum(bucket) 
     if sum_ >= k: 
      #don't need everything from this bucket 
      return solution + solve(bucket, k) 
     else: 
      k -= sum_ 
      solution += bucket 

print solve([5,2,7,52,30,12,18], 100) 
"[52, 30, 18]" 

Answer 4

मुझे विश्वास है कि "उप सरणी" शब्द सरणी से सटे हिस्सा (like here, उदाहरण के रूप में एक और समस्या का तात्पर्य)

तो न्यूनतम लंबाई (एस)

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

Answer 5

ओपी ने टिप्पणियों के जवाब में यह स्पष्ट किया है कि समस्या को ढूंढना है एक सबसेट, जरूरी नहीं कि एक संगत अनुक्रम (शब्द 'सबराय' स्वीकार्य रूप से गरीब था)। फिर, मेरा मानना ​​है कि mcdowella द्वारा इंगित विधि सही है, जिसमें निम्न चरणों को शामिल किया गया है:

एन तत्वों के साथ प्रारंभ करना, मेडियन तत्व (यानी (एन/2) -थ तत्व को सॉर्ट किए गए सरणी की कल्पना करना, जिसे आप नहीं करते हैं नहीं है और निर्माण नहीं है)। यह "मेडियन के मध्य" एल्गोरिदम के साथ प्राप्त किया गया है, ओ (एन) साबित हुआ है, विकी रेफ पहले से ही दिया गया है और यहां दोहराया गया है: Selection algorithm, see section on the Median of Median algorithm

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

स्कैन पूरा करने के बाद, यदि "ऊपरी आधा" -सम लक्ष्य (के) से ऊपर है, तो आप सभी को निचले आधे के बारे में भूल जाते हैं और ऊपरी आधे के लिए प्रक्रिया दोहराते हैं, जिसका आकार (लगभग) एन/2 है । यदि दूसरी तरफ, "ऊपरी आधा 'योग के मुकाबले कम है, तो आप अंतिम परिणाम में ऊपरी आधा जोड़ते हैं, इसके योग को घटाकर घटाते हैं और कम आधे से प्रक्रिया को दोहराते हैं।

कुल मिलाकर , आप आकार एन, एन/2, एन/4, एन/8 इत्यादि के सेट को संसाधित करते हैं, प्रत्येक ओ (एम) में उनके संबंधित आकार एम के संबंध में, और इसलिए समग्र सामग्री एन में भी रैखिक है, क्योंकि एन + एन/2 + एन/4 + N/8 ... 2N नीचे रहता है।

Answer 6

subarray सरणी की परिभाषा के द्वारा सन्निहित हो गया है।

2 उपयोग संकेत (शुरू, अंत)। उन्हें प्रारंभ करने के लिए

सरणी की शुरुआत। वर्तमान योग को ट्रैक करें (प्रारंभ करें, अंत), एक डी एक से एक के लिए सही अंत में। हर बार जब आप अंत पॉइंटर ले जाते हैं, sum = sum + array [end]।

और जब sum> = target, दाईं ओर से प्रारंभ करना प्रारंभ करें और sum = sum - array [start] के रूप में ट्रैकिंग को ट्रैक रखें।

दाएं से शुरू होने पर, राशि की जांच करना अभी भी लक्ष्य से कम नहीं है। और हमें लम्बाई = अंत - प्रारंभ + 1, साथ ही न्यूनतम लम्बाई = मिनट (न्यूनतम लंबाई, लंबाई) करके लंबाई को ट्रैक करने की भी आवश्यकता है।

अब जब हम दोनों पॉइंटर्स को यथासंभव सही स्थानांतरित कर चुके हैं, तो हमें केवल मिनी लम्बाई वापस करने की आवश्यकता है।

सामान्य विचार पहली बार "खिड़की" ढूंढना है जो स्थिति (sum> = target) को संतुष्ट करता है, फिर विंडो को एक ही समय में दाईं ओर स्लाइड करें और खिड़की के आकार को हर बार विंडो में ले जाएं।