किसी सरणी के अंदर तत्वों की दूरी प्राप्त करें?

Question

मैं एक आसान काम के साथ संघर्ष कर रहा हूं जिसमें गैर-ऋणात्मक पूर्णांक की एक श्रृंखला है जहां मुझे निकटतम दूरी वापस करने की आवश्यकता है।

सरणी: arr = [8, 24, 3, 20, 1, 17]

समाधान:

def smallest_distance(a) 
    result = nil 
    a.each_with_index do |item1, index1| 
    a.each_with_index do |item2, index2| 
     next if index1 == index2 
     temp = (item1 - item2) >= 0 ? item1 - item2 : item2 - item1 
     result = temp if result.nil? || temp < result 
    end 
    end 
    result 
end 

: 2, arr[2]-arr[4]

सोर तक, मैं केवल एक हे लिखने के लिए (एन^2) समाधान है, जो स्पष्ट रूप से पर्याप्त नहीं है प्रबंधित किया है

इस पर सुधार करने के तरीके पर कोई विचार?

Answer 1

समाधान सरणी को सॉर्ट करना है, और उसके बाद इसे पुनरारंभ करना है। अब आपको केवल (arr[i],arr[i+1]) के आस-पास के उम्मीदवारों की जांच करने की आवश्यकता है, न कि तत्वों की प्रत्येक जोड़ी।

यह O(NlogN) में चलता है।

ध्यान दें कि यह Element Distinctness Problem का सामान्यीकरण है, इसलिए यदि आप सबसे खराब केस प्रदर्शन में रूचि रखते हैं, तो आप O(NlogN) से बेहतर प्राप्त नहीं कर सकते हैं।

Answer 2

पोस्ट किया गया समाधान सही ढंग से n*log(n) समय है, जो सबसे तेज़ समय है कि एक समाधान पाया जा सकता है। उसके समाधान के लिए रूबी कोड इस प्रकार की रेखाओं के साथ कुछ दिखाई देगा:

def smallest_distance(a) 
    sorted = array.sort 
    shortest = 999999 # arbitrary large value 
    for i in 0..sorted.length 
    comparison = sorted[i+1] - sorted[i] if sorted[i+1] != nil 
    if comparison < shortest 
     shortest = comparison 
    end 
    end 
    return shortest 
end 

Answer 3

आमतौर पर इस तरह के ऐरे से संबंधित समस्या के लिए। यदि आपके पास ओ (एन^2) के बराबर या उससे भी बदतर एल्गोरिदम है तो आप इसे संसाधित करने के लिए सॉर्टिंग एल्गोरिदम का उपयोग करने पर हमेशा विचार कर सकते हैं। आमतौर पर ओ (एलएनजी) लेता है, उसके बाद आपके पास एक रैखिक एल्गोरिदम हो सकता है।

इस समस्या के लिए, आप इस सरणी को सॉर्ट कर सकते हैं। फिर बस एक लूप के लिए आसन्न तत्वों की तुलना करें। अंतिम परिणाम समय जटिलता ओ (एन लॉगन) है जो आपके मूल विचार से बेहतर है।

तो आप कर सकते हैं:

sorted = arr.sort 

फिर एक पाश

arr[i] with ar[i+1] from i = 0 ~ len-1