सबसे तेजी से एल्गोरिथ्म एक सरणी में सबसे अधिक आवृत्ति के साथ एक तत्व को खोजने के लिए क्या है

Question

मैं दो इनपुट सरणियों एक्स है और वाई मैं जो सरणी वाई में सर्वोच्च आवृत्ति के साथ होता है सरणी एक्स के उस तत्व लौटना चाहते

ऐसा करने का बेवकूफ तरीका यह है कि सरणी एक्स के प्रत्येक तत्व एक्स के लिए, मैं रैखिक रूप से इसकी घटनाओं की संख्या के लिए सरणी वाई खोजता हूं और उसके बाद उस तत्व x को वापस करता हूं जिसमें उच्चतम आवृत्ति होती है। यहाँ छद्म एल्गोरिथ्म है:

max_frequency = 0 
max_x = -1    // -1 indicates no element found 
For each x in X 
    frequency = 0 
    For each y in Y 
     if y == x 
      frequency++ 
    End For 
    If frequency > max_frequency 
     max_frequency = frequency 
     max_x = x 
    End If 
End For 
return max_x 

दो नेस्टेड छोरों देखते हैं, इस एल्गोरिथ्म के लिए समय जटिलता हे होगा (एन^2)। क्या मैं इसे ओ (nlogn) या तेज़ में कर सकता हूं?

Answer 1

उपयोग की गिनती के लिए एक हैश तालिका मानचित्रण कुंजी देता है। सरणी में प्रत्येक तत्व के लिए, counts[element] = counts[element] + 1 या अपनी भाषा के बराबर की तरह करें।

अंत में, हैश तालिका में मैपिंग के माध्यम से लूप करें और अधिकतम खोजें।

Answer 2

एक quicksort कर सकता है और फिर इसे एक चर के साथ पार कर सकता है जो गणना करता है कि कितने संख्या में एक पंक्ति है + वह संख्या क्या है। यही कारण है कि आप nlogn

Answer 3

मर्ज फूट डालो पर आधारित छँटाई देना चाहिए और जीतना संकल्पना आप ओ (nlogn) जटिलता

Answer 4

वैकल्पिक रूप से, यदि आपके पास अतिरिक्त डेटा संरचनाएं हो सकती हैं, तो आप एश तालिका में अपनी आवृत्ति को अपडेट करने वाले प्रत्येक नंबर के लिए सरणी वाई चलाते हैं। यह O(N(Y) समय लेता है। फिर एक्स को ढूंढें एक्स में कौन सा तत्व उच्चतम आवृत्ति है। यह O(N(X)) समय लेता है। कुल मिलाकर: रैखिक समय, और के बाद से आप कम से कम एक बार किसी भी कार्यान्वयन में X और Y दोनों के प्रत्येक तत्व को देखने के लिए है (संपादित: इस सख्ती से सभी मामलों में सच नहीं बोल रहा है/के रूप में jwpat7 अंक बाहर सभी कार्यान्वयन,, हालांकि यह सबसे बुरे मामले में सच है), आप इसे इससे भी तेज नहीं कर सकते हैं।

Answer 5

आम एल्गोरिदम के समय जटिलता नीचे सूचीबद्ध हैं:

Algorithm  | Best | Worst | Average 
--------------+-----------+-----------+---------- 
MergeSort  | O(n lg n) | O(n lg n) | O(n lg n) 
InsertionSort | O(n) | O(n^2) | O(n^2) 
QuickSort  | O(n lg n) | O(n^2) | O(n lg n) 
HeapSort  | O(n lg n) | O(n lg n) | O(n lg n) 
BinarySearch | O(1) | O(lg n) | O(lg n) 

सामान्य तौर पर, जब एक सूची के माध्यम से traversing एक निश्चित मानदंडों को पूरा करने के लिए, आप वास्तव में किसी भी रैखिक समय की तुलना में बेहतर नहीं कर सकते। यदि आपको सरणी को सॉर्ट करने की आवश्यकता है, तो मैं सरणी में उच्चतम आवृत्ति वाला तत्व ढूंढने के लिए विलय (बहुत भरोसेमंद) के साथ छड़ी कहूंगा।

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

Answer 6

आपका सुझाया गया दृष्टिकोण ओ (एन^2) होगा यदि दोनों सूचियां लंबाई एन हैं। अधिक संभावना है कि सूचियां अलग-अलग लंबाई हो सकती हैं, इसलिए समय जटिलता ओ (एमएन) के रूप में व्यक्त की जा सकती है।

आप दो चरणों में आपकी समस्या को अलग कर सकते हैं: 1. आदेश अद्वितीय उनकी आवृत्ति द्वारा Y से तत्वों 2. इस सूची है कि एक्स में मौजूद है

से पहले आइटम यह एक होमवर्क सवाल की तरह लगता है के रूप में प्राप्त करें मैं आपको इस बारे में सोचने दूँगा कि आप इन व्यक्तिगत कदमों को कितनी तेजी से कर सकते हैं। इन लागतों का योग आपको एल्गोरिदम की समग्र लागत देगा। ऐसे कई दृष्टिकोण हैं जो आपके पास वर्तमान में मौजूद दो सूची लंबाई के उत्पाद से सस्ता होंगे।

Answer 7

पहला चरण: एक्स और वाई दोनों को सॉर्ट करें। उनकी इसी लंबाई को मानना ​​मीटर और n, इस चरण की जटिलता O(n log n) + O(m log m) होगी।

2 कदम: गिनती प्रत्येक एक्स _मैंमें वाई और अब तक अधिकतम संख्या पर नज़र रखने के। हल कर वाई में एक्स _मैं की खोजें O(log n) है। कुल 2 कदम जटिलता है:

कुल जटिलता: O(n log n) + O(m log m) + O(m log n), या simpified: O(max(n,m) log n)

Answer 8

क्रमबद्ध एक्स और वाई तब तरह मर्ज है। X.

इतनी जटिलता, ओ (nlogn) + O (mlogm) + O (m + n) = O (klogk) जहां n, m = लंबाई की समानता के साथ हर बार वाई से आवृत्तियों की गणना करें एक्स, वाई; के = अधिकतम (एम, एन)