𝗟𝗲𝗲𝘁𝗰𝗼𝗱𝗲 𝟭𝟱𝟬 | 𝗗𝗮𝘆 𝟰: 𝗠𝗮𝗷𝗼𝗿𝗶𝘁𝘆 𝗘𝗹𝗲𝗺𝗲𝗻𝘁
Leetcode 169 ஒரு அணியில் (array) உள்ள பெரும்பான்மை உறுப்பை (majority element) கண்டறியச் சொல்கிறது. பெரும்பான்மை உறுப்பு n / 2 முறைக்கும் அதிகமாகத் தோன்றும். அது எப்போதும் இருக்கும் என்று நாம் கருதுகிறோம்.
இதை நீங்கள் இரண்டு வழிகளில் தீர்க்கலாம்.
அணுகுமுறை 1: Map முறை (The Map Method)
இந்த முறை ஒவ்வொரு எண்ணும் எத்தனை முறை தோன்றுகிறது என்பதைக் கணக்கிட ஒரு Map-ஐப் பயன்படுத்துகிறது.
- எண்ணிக்கையைச் சேமிக்க ஒரு Map-ஐ உருவாக்கவும்.
- அணியின் (array) வழியாக லூப் (loop) செய்யவும்.
- ஒவ்வொரு எண்ணின் எண்ணிக்கையையும் புதுப்பிக்கவும்.
- n / 2-க்கும் அதிகமான எண்ணிக்கையைக் கொண்ட எண்ணைக் கண்டறிய Map வழியாக லூப் செய்யவும்.
சிக்கல்தன்மை (Complexity):
- நேரம் (Time): O(n), ஏனெனில் நீங்கள் இரண்டு தொடர்ச்சியான லூப்களைப் பயன்படுத்துகிறீர்கள்.
- இடம் (Space): O(n), ஏனெனில் தனித்துவமான உறுப்புகளின் எண்ணிக்கைக்கு ஏற்ப Map வளர்கிறது.
அணுகுமுறை 2: Boyer-Moore Voting Algorithm
இது நிலையான நினைவகத்தைப் (constant memory) பயன்படுத்திப் பிரச்சனையைத் தீர்க்கும் ஒரு மேம்படுத்தப்பட்ட வழியாகும்.
எண்களை ஒன்றுக்கொன்று எதிரான அணிகளாகக் கருதவும். ஒவ்வொரு முறையும் ஒரு எண் மற்றொரு வேறுபட்ட எண்ணைச் சந்திக்கும்போது, அவை ஒன்றையொன்று ரத்து செய்துவிடும். பெரும்பான்மை உறுப்பு பாதி நேரத்திற்கும் மேலாகத் தோன்றுவதால், அது எப்போதும் இறுதியில் நிலைத்து நிற்கும்.
இது எவ்வாறு செயல்படுகிறது:
- ஒரு வேட்பாளரைத் (candidate) தேர்ந்தெடுத்து, எண்ணிக்கையை (count) 0 என அமைக்கவும்.
- அணியின் வழியாக லூப் செய்யவும்.
- எண்ணிக்கை 0 ஆக இருந்தால், தற்போதைய எண்ணை வேட்பாளராக அமைக்கவும்.
- தற்போதைய எண் வேட்பாளருடன் பொருந்தினால், எண்ணிக்கையை 1 அதிகரிக்கவும்.
- பொருந்தவில்லை என்றால், எண்ணிக்கையை 1 குறைக்கவும்.
சிக்கல்தன்மை (Complexity):
- நேரம் (Time): O(n), ஏனெனில் நீங்கள் அணியின் வழியாக ஒரு முறை மட்டுமே செல்கிறீர்கள்.
- இடம் (Space): O(1), ஏனெனில் நீங்கள் இரண்டு மாறிகளை (variables) மட்டுமே பயன்படுத்துகிறீர்கள்.
இது ஏன் முக்கியமானது:
இரண்டு முறைகளுமே O(n) காலச் சிக்கல்தன்மையைக் கொண்டுள்ளன. இருப்பினும், இரண்டாவது அணுகுமுறை மிகக் குறைந்த நினைவகத்தையே பயன்படுத்துகிறது. இதற்கு Map தேவையில்லை. இது பெரிய தரவுத் தொகுப்புகளுக்கு (large datasets) சிறந்தது.
ஆதாரம்: https://dev.to/afuji/leetcode-150-day-4-majority-element-naive-vs-optimized-eo6