Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> Python

Python में क्वेरीज़ से निकटतम कमरा खोजें

कमरों की सूची (roomId, size) और क्वेरीज़ (preferred, minSize) दी गई हैं। प्रत्येक क्वेरी के लिए: आकार ≥ minSize वाला कमरा खोजें जिसका |roomId - preferred| न्यूनतम हो। टाई में छोटी roomId चुनें। ऐसा कमरा न हो तो -1।

एल्गोरिदम: ऑफलाइन प्रोसेसिंग + बाइनरी सर्च

  1. कमरों को आकार के अनुसार आरोही क्रम में सॉर्ट करें
  2. क्वेरीज़ को (preferred, minSize, index) में बदलें और minSize के अनुसार अवरोही क्रम में सॉर्ट करें
  3. सॉर्टेड कंटेनर (बाइनरी सर्च के लिए सॉर्टेड सूची) में योग्य कमरे जोड़ें
  4. प्रत्येक क्वेरी के लिए बाइनरी सर्च से निकटतम roomId खोजें

Python कार्यान्वयन


import bisect

def closest_room(rooms, queries):
    # कमरे: आकार द्वारा आरोही, टाई में roomId द्वारा
    rooms.sort(key=lambda x: (x[1], x[0]))
    
    # क्वेरीज़: (preferred, minSize, original_index)
    queries = [(qid, size, i) for i, (qid, size) in enumerate(queries)]
    # minSize अवरोही, टाई में preferred, फिर index
    queries.sort(key=lambda x: (x[1], x[0], x[2]), reverse=True)
    
    ans = [-1] * len(queries)
    sorted_ids = []  # सॉर्टेड roomIds (bisect के लिए)
    
    for qid, size, i in queries:
        # सभी कमरे जिनका आकार ≥ size, sorted_ids में डालें
        while rooms and rooms[-1][1] >= size:
            room_id, _ = rooms.pop()
            bisect.insort(sorted_ids, room_id)
        
        if sorted_ids:
            # बाइनरी सर्च: qid डालने की स्थिति
            j = bisect.bisect(sorted_ids, qid)
            
            if j == len(sorted_ids):
                # सभी roomId < qid, सबसे बड़ा चुनें
                ans[i] = sorted_ids[-1]
            elif j == 0:
                # सभी roomId > qid, सबसे छोटा चुनें
                ans[i] = sorted_ids[0]
            else:
                # दोनों तरफ उम्मीदवार, निकटतम चुनें
                left = sorted_ids[j-1]
                right = sorted_ids[j]
                if right - qid < qid - left:
                    ans[i] = right
                else:
                    ans[i] = left  # टाई में छोटा (left)
    
    return ans

# परीक्षण
rooms = [[2,2], [1,2], [3,2]]
queries = [[3,1], [3,3], [5,2]]
print(closest_room(rooms, queries))  # [3, -1, 3]

व्याख्या

क्वेरीयोग्य कमरे (size≥minSize)निकटतम preferredउत्तर
[3,1]सभी (size=2≥1)room 3 (|3-3|=0)3
[3,3]कोई नहीं (सभी size=2<3)--1
[5,2]सभी (size=2≥2)room 3 (|3-5|=2)3

जटिलता

  • समय: O((n + q) log n) - सॉर्टिंग + बाइनरी सर्च/इन्सर्ट
  • स्थान: O(n + q)

मुख्य बिंदु

  • कमरों और क्वेरीज़ दोनों को सॉर्ट करके "ऑफलाइन" प्रोसेसिंग
  • bisect.insort सॉर्टेड सूची बनाए रखता है O(log n) इन्सर्ट में
  • bisect.bisect इन्सर्शन पॉइंट देता है O(log n)
  • बड़े इनपुट के लिए रैखिक स्कैन से बहुत तेज़
  1. - पायथन में दो लिंक्ड लिस्ट से इंटरसेक्शन खोजने का प्रोग्राम

    मान लीजिए हमारे पास दो सॉर्टेड लिंक्ड लिस्ट L1 और L2 हैं, हमें एक नई सॉर्टेड लिंक्ड लिस्ट बनानी है जिसमें इन दोनों लिस्ट का इंटरसेक्शन हो।उदाहरण के लिए, यदि इनपुट L1 = [2, 4, 8] और L2 = [3, 4, 8, 10] है, तो आउटपुट [4, 8] होगा।समाधान दृष्टिकोणइसे हल करने के लिए हम निम्नलिखित चरणों का पालन करेंगे (टू-

  1. पायथन प्रोग्राम: दो क्रमबद्ध सरणियों से निकटतम जोड़ी खोजें पायथन प्रोग्राम: दो क्रमबद्ध सरणियों से निकटतम जोड़ी खोजें

    इस लेख में हम दी गई समस्या के समाधान के बारे में जानेंगे। समस्या कथन हमें दो सरणियाँ दी गई हैं, हमें दो क्रमबद्ध सरणियों से निकटतम जोड़ी खोजने की आवश्यकता है। उदाहरण # sys मॉड्यूल import sys # जोड़ी def print_(ar1, ar2, m, n, x): # अंतर diff = sys.maxsize # इंडेक्स l = 0 r = n-1

  1. - पायथन प्रोग्राम सूची से N सबसे बड़े तत्व खोजने के लिए

    एक पूर्णांक सूची दी गई है, हमारा कार्य सूची में N सबसे बड़े तत्व ढूंढना है। उदाहरण इनपुट : [40, 5, 10, 20, 9] N = 2 आउटपुट: [40, 20] एल्गोरिदम चरण 1: एक पूर्णांक सूची और सबसे बड़ी संख्या की संख्या इनपुट करें। चरण 2: पहले सूची को N बार पार करें। चरण 3: प्रत्येक पारगमन में सबसे बड़ा मान ढूंढें और इसे