11
आप एक पास में अज्ञात लंबाई के साथ लिंक्ड सूची में एक समान यादृच्छिक तत्व कैसे लेंगे या दो पास नहीं होंगे?अज्ञात लंबाई के साथ लिंक्ड सूची में आप एक समान यादृच्छिक तत्व कैसे चुनेंगे?
A
उत्तर
22
जलाशय नमूना http://en.wikipedia.org/wiki/Reservoir_sampling का उपयोग करें। आपको डेटा के केवल एक ही पास की आवश्यकता है।
एक तत्व उठा लिए: kth तत्व के लिए,
- पहला तत्व उठाओ (संभावना 1)
- बाद में यह संभावना 1/k साथ लेने (यानी kth तत्व के साथ मौजूदा चयन की जगह)
मैं आपको यह साबित करने दूंगा कि यह परिणाम तत्वों के समान चयन में हैं।
+0
मैंने इसका उपयोग करने की कोशिश की लेकिन यह के यादृच्छिक तत्वों को चुन देगा। लेकिन मुझे केवल पहले तत्व का चयन करने की आवश्यकता होगी – exlux15
+0
@ एनीलबूरूरम के = 1 का उपयोग करें? वैसे भी, पोस्ट में वर्णित एल्गोरिदम (विकी नहीं) एक तत्व मामले के लिए है। – ElKamina
+1
ठीक है अगर मैं सूची को पार करने के लिए ++ लंबाई के साथ थोड़ी देर लूप का उपयोग करता हूं। यदि मैं i = rand()% लंबाई का उपयोग करता हूं, तो क्या मैं वर्तमान नोड पर यादृच्छिक पसंद करूंगा? – exlux15
संबंधित मुद्दे
- 1. क्लोजर में आप एक सूची को यादृच्छिक कैसे करते हैं?
- 2. जावा में लिंक्ड सूचियों की लिंक्ड सूची
- 3. एक लिंक्ड सूची
- 4. एक लिंक्ड सूची में भ्रष्ट सूचक
- 5. अज्ञात लंबाई
- 6. एक समान यादृच्छिक संख्या जनरेटर
- 7. स्कैला लिंक्ड सूची stackoverflow
- 8. मल्टीथ्रेडेड लिंक्ड सूची ट्रैवर्सल
- 9. लिंक्ड सूची समारोह
- 10. लिंक्ड सूची की सरणी के साथ काम कर
- 11. सी ++ लिंक्ड सूची व्यवहार
- 12. लिंक्ड सूची
- 13. अज्ञात आकार सूची के बीच
- 14. आप एक लिंक्ड सूची को दूसरी सूची में कैसे कॉपी करते हैं?
- 15. किसी लिंक्ड सूची में भ्रष्टाचार ढूँढना
- 16. शुद्ध फ़ंक्शन में यादृच्छिक सूची तत्व कैसे चुनें?
- 17. जावा में लिंक्डलिस्ट क्यों एक वास्तविक लिंक्ड सूची नहीं है?
- 18. एक लिंक्ड सूची थ्रेड सुरक्षित बनाएं
- 19. समान तर्कों के साथ लूप में अज्ञात फ़ंक्शंस बनाना
- 20. अज्ञात लंबाई के अनुक्रम से यादृच्छिक रूप से एन आइटम उठाएं
- 21. आप प्रत्येक तत्व को एक सूची में एक सूची में कैसे विभाजित करते हैं?
- 22. पार्सिंग बाइट सरणी अज्ञात लंबाई
- 23. एक लिंक्ड सूची में साइकिल का पता लगाने: संपूर्ण सिद्धांत
- 24. मानचित्र में यादृच्छिक तत्व
- 25. समान लंबाई तार
- 26. आर की सूची में यादृच्छिक तत्व का चयन करें?
- 27. एक डबल-लिंक्ड सूची साफ़ करना
- 28. शब्दों की सूची की एक और लंबाई लंबाई शब्दों के साथ विम प्रतिस्थापन?
- 29. MATLAB में अज्ञात लंबाई का मैट्रिक्स?
- 30. ज्ञात पैरामीटर प्रकारों के साथ एक चर लंबाई के साथ एक तर्क सूची दस्तावेज़ कैसे दस्तावेज़?
मुझे डर है कि आपको अपने प्रश्न में थोड़ा और प्रयास करना होगा और आप क्रिस्टल को स्पष्ट कर सकते हैं कि आप क्या पूछ रहे हैं –
ठीक है। अज्ञात लंबाई के साथ लिंक्ड सूची में आप एक समान यादृच्छिक तत्व कैसे चुनेंगे? – exlux15
यदि यह आपका प्रश्न है, तो यह एक दिलचस्प सवाल है। कृपया तदनुसार अपना प्रश्न संपादित करें और मैं इसे –