संख्याओं की संख्या और बड़ी संख्या में कैसे?

Question

मेरे पास सॉर्ट किए गए सकारात्मक पूर्णांक के 200 सरणी हैं (उनमें से कुछ में लाखों से अधिक संख्याएं हैं)। मुझे प्रत्येक सरणी में मौजूद पहला नंबर ढूंढना होगा। आप क्या सुझाव देंगे?

Answer 1

• प्रत्येक सरणी पर एक इंडेक्स रखें।
• संदर्भ के रूप में पहली सरणी की पहली संख्या के साथ प्रारंभ करें।
• संदर्भ से कम एन-वें सरणी की पहली संख्या है, इसकी अनुक्रमणिका बढ़ाएं।
• संदर्भ के बराबर एन-वें सरणी की पहली संख्या है, एन बढ़ाएं और आगे बढ़ें - अगली सरणी।
• संदर्भ से अधिक एन-वें सरणी की पहली संख्या है, उस संख्या का संदर्भ संदर्भ के रूप में उपयोग करें और शुरू करें।
• यदि n == 201, आपका संदर्भ प्रत्येक सरणी में मौजूद है।

संपादित करें: एक कोड उदाहरण:

while n < len(data): 
    item = data[n][indices[n]] 
    if item < reference: 
     indices[n] += 1 
    elif item == reference: 
     n += 1 
    elif item > reference: 
     reference = item 
     n = 0 

print reference 

Answer 2

आप सरणी पर के-वे विलय कर सकते हैं और k बार दिखाई देने वाले पहले तत्व की जांच कर सकते हैं।

एक विकल्प histogram बना रहा है, और हिस्टोग्राम में k समय दिखाई देने वाला पहला तत्व चुना है। जावा में एक हिस्टोग्राम एक Map<Element,Integer>

द्वारा आसानी से लागू किया जा सकता है दोनों समाधान O(kn) हैं जहां k सरणियों की संख्या है और n एक सरणी के औसत आकार है, तो यह मूल रूप इनपुट के आकार में रैखिक है।