दिलचस्प पोस्ट
क्रोम पैक एप और क्रोम एक्सटेंशन के बीच संचार करना है? एसक्यूएल में शामिल होने के मामले क्या है? एंड्रॉइड में PostExecute की गतिविधि को सही ढंग से कैसे प्रारंभ करें? कॉलबैक जब निर्भरता संपत्ति को एक्सएमएल परिवर्तन प्राप्त होता है फिर से संकलन करते समय बाइनरी आउटपुट बराबर क्यों नहीं है? पूर्ण पोस्टबैक के बिना AJAX updatepanel में फ़ाइल अपलोडिंग org.glassfish.jersey.servlet.ServletContainer क्लास नोटफ़ाउंड अपवाद Google मानचित्र पूरी तरह से पृष्ठ पर रेंडर नहीं कर रहा है? जावा: ऐरे सूचकांक सीमा से बाहर अपवाद 'निजी वैल' और 'निजी फाइनल वैल' क्यों अलग हैं? थ्रेडलोकल एंड मेमरी लीक क्या इसमें $ _SERVER का उपयोग करना एक अच्छा विचार है? जीसीसी के ## __ वीए_एआरजीएस_ चाल के मानक विकल्प? Excel फ़ाइल में डेटाटाइल निर्यात करें स्ट्रिंग के संभव संयोजन प्रदर्शित करें

कम से कम एन / 2 बार दोहराया जाने वाला सरणी का तत्व कैसे खोजता है?

एन तत्वों के साथ एक सरणी को देखते हुए हम जानते हैं कि उन तत्वों में से एक को कम से कम एन / 2 बार दोहराता है

हम अन्य तत्वों के बारे में कुछ नहीं जानते वे दोहरा सकते हैं या अद्वितीय हो सकते हैं

क्या तत्व पता लाने का कोई तरीका है जो एक पास में कम से कम एन / 2 बार दोहराता है या हे (एन) हो सकता है?

उपयोग करने के लिए कोई अतिरिक्त स्थान नहीं है।

Solutions Collecting From Web of "कम से कम एन / 2 बार दोहराया जाने वाला सरणी का तत्व कैसे खोजता है?"

st0le ने सवाल का उत्तर दिया, लेकिन यहां एक 5minute कार्यान्वयन है:

 #include <stdio.h> #define SIZE 13 int boyerMoore(int arr[]) { int current_candidate = arr[0], counter = 0, i; for (i = 0; i < SIZE; ++i) { if (current_candidate == arr[i]) { ++counter; printf("candidate: %i, counter: %i\n",current_candidate,counter); } else if (counter == 0) { current_candidate = arr[i]; ++counter; printf("candidate: %i, counter: %i\n",current_candidate,counter); } else { --counter; printf("candidate: %i, counter: %i\n",current_candidate,counter); } } return current_candidate; } int main() { int numbers[SIZE] = {5,5,5,3,3,1,1,3,3,3,1,3,3}; printf("majority: %i\n", boyerMoore(numbers)); return 0; } 

और यहां एक मजेदार व्याख्या है (कम से कम कागज पढ़ने से ज्यादा मज़ा): http://userweb.cs.utexas.edu/~moore/best-ideas/mjrty/index.html

जैसा कि अन्य उपयोगकर्ता पहले से ही एल्गोरिथम पोस्ट कर चुके हैं, मैं इसे दोहराना नहीं दूंगा। हालांकि, मैं यह क्यों काम करता है के रूप में एक सरल स्पष्टीकरण प्रदान करता है:

निम्न आरेख पर विचार करें, जो कि वास्तव में अप्रकाशित प्रकाश का आरेख है:

केंद्र से निकलने वाली तीर

केंद्र से प्रत्येक तीर एक अलग उम्मीदवार का प्रतिनिधित्व करता है। काउंटर और उम्मीदवार का प्रतिनिधित्व करने वाले तीर पर कहीं एक बिंदु की कल्पना करो। शुरू में काउंटर शून्य पर है, इसलिए यह केंद्र में शुरू होता है।
जब वर्तमान उम्मीदवार पाया जाता है, तो वह उस तीर की दिशा में एक कदम ले जाता है यदि एक अलग मान पाया जाता है, तो काउंटर केंद्र की तरफ एक कदम ले जाता है।
यदि बहुमत मूल्य है, तो आधे से ज्यादा चालें उस तीर की ओर होंगी, और इसलिए एल्गोरिथ्म वर्तमान उम्मीदवार के साथ समाप्त हो जाएगा जो बहुमत वाला मूल्य है।

द बॉयर-मूर बहुमत वोट एल्गोरिदम

 //list needs to have an element with a count of more than n/2 throughout itself for //this algorithm to work properly at all times. lst = [1,2,1,2,3,1,3,3,1,2,1,1,1] currentCount = 0 currentValue = lst[0] for val in lst: if val == currentValue: currentCount += 1 else: currentCount -= 1 if currentCount == 0: currentValue = val currentCount = 1 print(currentValue) 

यह कोड जिस तरह से हम एक तत्व के बहुमत मिल के लिए एक समान कार्यान्वयन है

 int find(int* arr, int size) { int count = 0, i, m; for (i = 0; i < size; i++) { if (count == 0) m = arr[i]; if (arr[i] == m) count++; else count--; } return m; } 

अतिरिक्त स्थान का उपयोग किए बिना कुछ भी गणना करना संभव नहीं लगता है। आपको कहीं कम से कम एक काउंटर को स्टोर करना होगा यदि आप कहते हैं कि आप ओ (एन) स्पेस से अधिक उपयोग नहीं कर सकते हैं तो यह काफी आसान होना चाहिए।

एक तरह से मूल सूची से केवल अनूठी वस्तुओं की दूसरी सूची बनाना होगा। फिर, सूची में प्रत्येक आइटम की घटनाओं की संख्या के लिए एक काउंटर के साथ दूसरे के रूप में एक तीसरी सूची बनाओ।

एक और तरीका यह है कि सूची को क्रमबद्ध करने के लिए सबसे बड़ा सटे खंड मिल जाए।

दाविद के उत्तर के लिए एफएफओ द्वारा सुझाए गए संशोधनों का उपयोग करना:

 public class MaxRepeated { public static void main(final String[] args) { maxRepeatedElement(new int[]{1, 2, 1, 2, 3, 2, 3, 1}); maxRepeatedElement(new int[]{1, 2, 1, 2, 3, 1, 3, 1}); maxRepeatedElement(new int[]{1, 2, 1, 2, 4, 1, 1, 3, 1, 3, 1}); maxRepeatedElement(new int[]{1, 2, 1, 2, 2, 1, 2, 3, 1, 2, 1, 2}); } private static int maxRepeatedElement(final int[] arr) { int current_candidate = arr[0]; int previous_candidate = arr[0]; int counter = 0, i; for (i = 0; i < arr.length; ++i) { if (current_candidate == arr[i]) { ++counter; } else if (counter == 0) { previous_candidate = current_candidate; current_candidate = arr[i]; ++counter; } else { --counter; } System.out.printf(" candidate: %d, counter: %d\n", current_candidate, counter); } if (counter == 0) { System.out.printf(" possible: %d or %d with net freq %d \n", current_candidate, previous_candidate, counter); final int f1 = frequency(arr, current_candidate); final int f2 = frequency(arr, previous_candidate); final int halfLen = arr.length / 2 + (arr.length % 2 == 0 ? 0 : 1); if (f1 >= halfLen || f2 >= halfLen) { if (f1 > f2) { System.out.printf("majority: %d with freq %d \n", current_candidate, f1); } else { System.out.printf("majority: %d with freq %d \n", previous_candidate, f2); } } else { System.out.printf("NO majority! \n"); } } else { System.out.printf("majority: %d with freq %d \n", current_candidate, frequency(arr, current_candidate)); } return current_candidate; } private static int frequency(final int[] arr, final int candidate) { int counter = 0; for (int c : arr) { counter += candidate == c ? 1 : 0; } return counter; } } 

इसे इस्तेमाल करे :

 #include<iostream> using namespace std; int main() { int counter=0; int a[]={10, 11, 5, 27, 4, 2, 7, 5, 7, 11, 9, 5, 5, 4, 10, 7, 5, 3, 7, 5}; for(int i = 0; i < 20; i++) { if(a[i]==5) counter++; } cout << "it appears " << counter << " times"; } 

बॉयर-मूर बहुमत वोट एल्गोरिदम नीचे इनपुट एरे में सही बहुमत खोजने में विफल रहता है

इंट संख्या [SIZE] = {1,2,3,4,1,2,3,4,1,2,3,4};

इंट संख्या [SIZE] = {1,2,3,4,1,2,3,4,1,2,3,4,1};