13
इस प्रकार मैं एक समस्या है जो सोचा:ढूँढना एक श्रेणी में निकटतम संख्या
हम आकार n का पूर्णांक की एक सरणी एक है, और हम परीक्षण मामलों टी है और हर परीक्षण मामलों में हम एक नंबर मीटर दिए गए हैं और एक सीमा [एस, ई] यानी हमें एस और ई दिया जाता है और हमें उस सरणी (ए [एस]-ए [ई]) की सीमा में एम की सबसे नज़दीकी संख्या मिलनी है।
आप मान सकते हैं कि अनुक्रमित सरणी 1 से n तक है।
उदाहरण के लिए:
A = {5, 12, 9, 18, 19}
m = 13
s = 4 and e = 5
तो जवाब 18.
प्रतिबन्ध होना चाहिए:
n<=10^5
t<=n
सभी मैं सोचा एक हे (एन) हर परीक्षण मामले के लिए समाधान है कर सकते हैं, और मुझे लगता है कि एक बेहतर समाधान मौजूद है।
यदि यह किसी भी तरह से क्रमबद्ध नहीं है, तो आपको ए [एस] और ए [ई] के बीच हर मूल्य का उपयोग करना होगा, इसलिए ओ (एन) यह है।या बल्कि ओ (ई-एस), मुझे लगता है। – femtoRgon
@femtoRgon मुझे पता है, लेकिन किसी भी डेटा strucxture के उपयोग से मुझे लगता है कि यह संभव है (बस सोचो लेकिन यकीन नहीं)। –
चूंकि आपने अधिकतम आकार सीमा (10^5) निर्दिष्ट की है, जटिलता ओ (1) नहीं है - यानी निरंतर समय? – Chris