𝗟𝗲𝗲𝘁𝗰𝗼𝗱𝗲 𝟭𝟱𝟬 | 𝗗𝗮𝘆 𝟰: 𝗠𝗮𝗷𝗼𝗿𝗶𝘁𝘆 𝗘𝗹𝗲𝗺𝗲𝗻𝘁
Leetcode 169 ಒಂದು array ನಲ್ಲಿರುವ majority element ಅನ್ನು ಕಂಡುಹಿಡಿಯಲು ಕೇಳುತ್ತದೆ. Majority element ಎಂಬುದು n / 2 ಬಾರಿಗಿಂತ ಹೆಚ್ಚು ಬಾರಿ ಕಾಣಿಸಿಕೊಳ್ಳುತ್ತದೆ. ಅದು ಯಾವಾಗಲೂ ಇರುತ್ತದೆ ಎಂದು ನಾವು ಭಾವಿಸುತ್ತೇವೆ.
ಇದನ್ನು ನೀವು ಎರಡು ವಿಧಾನಗಳಲ್ಲಿ ಪರಿಹರಿಸಬಹುದು.
Approach 1: The Map Method
ಈ ವಿಧಾನವು ಪ್ರತಿ ಸಂಖ್ಯೆಯು ಎಷ್ಟು ಬಾರಿ ಕಾಣಿಸಿಕೊಳ್ಳುತ್ತದೆ ಎಂಬುದನ್ನು ಎಣಿಸಲು Map ಅನ್ನು ಬಳಸುತ್ತದೆ.
- ಎಣಿಕೆಗಳನ್ನು (counts) ಸಂಗ್ರಹಿಸಲು ಒಂದು Map ಅನ್ನು ರಚಿಸಿ.
- Array ಮೂಲಕ ಲೂಪ್ ಮಾಡಿ.
- ಪ್ರತಿ ಸಂಖ್ಯೆಯ ಎಣಿಕೆಯನ್ನು ಅಪ್ಡೇಟ್ ಮಾಡಿ.
- n / 2 ಕ್ಕಿಂತ ಹೆಚ್ಚಿನ ಎಣಿಕೆ ಇರುವ ಸಂಖ್ಯೆಯನ್ನು ಕಂಡುಹಿಡಿಯಲು Map ಮೂಲಕ ಲೂಪ್ ಮಾಡಿ.
Complexity:
- Time: O(n) ಏಕೆಂದರೆ ನೀವು ಎರಡು ಸರಣಿ ಲೂಪ್ಗಳನ್ನು ಬಳಸುತ್ತೀರಿ.
- Space: O(n) ಏಕೆಂದರೆ ವಿಶಿಷ್ಟ ಅಂಶಗಳ (unique elements) ಸಂಖ್ಯೆಯೊಂದಿಗೆ Map ಬೆಳೆಯುತ್ತದೆ.
Approach 2: Boyer-Moore Voting Algorithm
ಇದು ಸ್ಥಿರ ಮೆಮೊರಿಯನ್ನು (constant memory) ಬಳಸಿಕೊಂಡು ಸಮಸ್ಯೆಯನ್ನು ಪರಿಹರಿಸುವ ಒಂದು ಉತ್ತಮವಾದ (optimized) ವಿಧಾನವಾಗಿದೆ.
ಸಂಖ್ಯೆಗಳನ್ನು ಪರಸ್ಪರ ವಿರೋಧಿಸುವ ತಂಡಗಳೆಂದು ಭಾವಿಸಿ. ಪ್ರತಿ ಬಾರಿ ಒಂದು ಸಂಖ್ಯೆಯು ಬೇರೆ ಸಂಖ್ಯೆಯನ್ನು ಭೇಟಿಯಾದಾಗ, ಅವು ಪರಸ್ಪರ ರದ್ದಾಗುತ್ತವೆ (cancel each other out). Majority element ಅರ್ಧಕ್ಕಿಂತ ಹೆಚ್ಚು ಬಾರಿ ಕಾಣಿಸಿಕೊಳ್ಳುವುದರಿಂದ, ಅದು ಯಾವಾಗಲೂ ಕೊನೆಯಲ್ಲಿ ಉಳಿಯುತ್ತದೆ.
How it works:
- ಒಂದು ಅಭ್ಯರ್ಥಿಯನ್ನು (candidate) ಆರಿಸಿ ಮತ್ತು ಎಣಿಕೆಯನ್ನು (count) 0 ಗೆ ಹೊಂದಿಸಿ.
- Array ಮೂಲಕ ಲೂಪ್ ಮಾಡಿ.
- ಎಣಿಕೆಯು 0 ಆಗಿದ್ದರೆ, ಪ್ರಸ್ತುತ ಸಂಖ್ಯೆಯನ್ನು ಅಭ್ಯರ್ಥಿಯನ್ನಾಗಿ ನಿಗದಿಪಡಿಸಿ.
- ಪ್ರಸ್ತುತ ಸಂಖ್ಯೆಯು ಅಭ್ಯರ್ಥಿಯೊಂದಿಗೆ ಹೊಂದಿಕೆಯಾದರೆ, ಎಣಿಕೆಯನ್ನು 1 ರಿಂದ ಹೆಚ್ಚಿಸಿ.
- ಅದು ಹೊಂದಿಕೆಯಾಗದಿದ್ದರೆ, ಎಣಿಕೆಯನ್ನು 1 ರಿಂದ ಕಡಿಮೆ ಮಾಡಿ.
Complexity:
- Time: O(n) ಏಕೆಂದರೆ ನೀವು array ಮೂಲಕ ಕೇವಲ ಒಂದು ಬಾರಿ ಹಾದುಹೋಗುತ್ತೀರಿ.
- Space: O(1) ಏಕೆಂದರೆ ನೀವು ಕೇವಲ ಎರಡು ವೇರಿಯೇಬಲ್ಗಳನ್ನು ಬಳಸುತ್ತೀರಿ.
Why it matters:
ಎರಡೂ ವಿಧಾನಗಳು O(n) ಸಮಯದ ಸಂಕೀರ್ಣತೆಯನ್ನು ಹೊಂದಿವೆ. ಆದಾಗ್ಯೂ, ಎರಡನೇ ವಿಧಾನವು ಬಹಳ ಕಡಿಮೆ ಮೆಮೊರಿಯನ್ನು ಬಳಸುತ್ತದೆ. ಇದಕ್ಕೆ Map ಅಗತ್ಯವಿಲ್ಲ. ಇದು ದೊಡ್ಡ ಡೇಟಾ ಸೆಟ್ಗಳಿಗೆ (large datasets) ಉತ್ತಮವಾಗಿದೆ.
Source: https://dev.to/afuji/leetcode-150-day-4-majority-element-naive-vs-optimized-eo6