𝗟𝗲𝗲𝘁𝗰𝗼𝗱𝗲 𝟭𝟱𝟬 | 𝗗𝗮𝘆 𝟰: 𝗠𝗮𝗷𝗼𝗿𝗶𝘁𝘆 𝗘𝗹𝗲𝗺𝗲𝗻𝘁
Leetcode 169 ਤੁਹਾਨੂੰ ਇੱਕ ਐਰੇ (array) ਵਿੱਚ Majority Element ਲੱਭਣ ਲਈ ਕਹਿੰਦਾ ਹੈ। Majority Element n / 2 ਵਾਰ ਤੋਂ ਵੱਧ ਵਾਰ ਆਉਂਦਾ ਹੈ। ਅਸੀਂ ਮੰਨਦੇ ਹਾਂ ਕਿ ਇਹ ਹਮੇਸ਼ਾ ਮੌਜੂਦ ਹੁੰਦਾ ਹੈ।
ਤੁਸੀਂ ਇਸਨੂੰ ਦੋ ਤਰੀਕਿਆਂ ਨਾਲ ਹੱਲ ਕਰ ਸਕਦੇ ਹੋ।
Approach 1: The Map Method
ਇਹ ਵਿਧੀ ਹਰੇਕ ਨੰਬਰ ਕਿੰਨੀ ਵਾਰ ਆਉਂਦਾ ਹੈ, ਇਸਦੀ ਗਿਣਤੀ ਕਰਨ ਲਈ ਇੱਕ Map ਦੀ ਵਰਤੋਂ ਕਰਦੀ ਹੈ।
- ਗਿਣਤੀ ਸਟੋਰ ਕਰਨ ਲਈ ਇੱਕ Map ਬਣਾਓ।
- ਐਰੇ (array) ਵਿੱਚ ਲੂਪ ਚਲਾਓ।
- ਹਰੇਕ ਨੰਬਰ ਲਈ ਗਿਣਤੀ ਅਪਡੇਟ ਕਰੋ।
- ਉਸ ਨੰਬਰ ਨੂੰ ਲੱਭਣ ਲਈ Map ਵਿੱਚ ਲੂਪ ਚਲਾਓ ਜਿਸਦੀ ਗਿਣਤੀ n / 2 ਤੋਂ ਵੱਧ ਹੋਵੇ।
Complexity:
- Time: O(n) ਕਿਉਂਕਿ ਤੁਸੀਂ ਦੋ ਲਗਾਤਾਰ ਲੂਪਸ ਦੀ ਵਰਤੋਂ ਕਰਦੇ ਹੋ।
- Space: O(n) ਕਿਉਂਕਿ Map ਵਿਲੱਖਣ (unique) ਅੰਕਾਂ ਦੀ ਗਿਣਤੀ ਦੇ ਨਾਲ ਵਧਦਾ ਹੈ।
Approach 2: Boyer-Moore Voting Algorithm
ਇਹ ਸਥਿਰ ਮੈਮੋਰੀ (constant memory) ਦੀ ਵਰਤੋਂ ਕਰਕੇ ਸਮੱਸਿਆ ਨੂੰ ਹੱਲ ਕਰਨ ਦਾ ਇੱਕ ਅਨੁਕੂਲਿਤ (optimized) ਤਰੀਕਾ ਹੈ।
ਨੰਬਰਾਂ ਨੂੰ ਵਿਰੋਧੀ ਟੀਮਾਂ ਵਜੋਂ ਸਮਝੋ। ਹਰ ਵਾਰ ਜਦੋਂ ਇੱਕ ਨੰਬਰ ਕਿਸੇ ਦੂਜੇ ਵੱਖਰੇ ਨੰਬਰ ਨਾਲ ਮਿਲਦਾ ਹੈ, ਤਾਂ ਉਹ ਇੱਕ ਦੂਜੇ ਨੂੰ ਖਤਮ (cancel) ਕਰ ਦਿੰਦੇ ਹਨ। ਕਿਉਂਕਿ Majority Element ਅੱਧੇ ਤੋਂ ਵੱਧ ਸਮੇਂ ਲਈ ਆਉਂਦਾ ਹੈ, ਇਸ ਲਈ ਇਹ ਹਮੇਸ਼ਾ ਅੰਤ ਵਿੱਚ ਬਚਿਆ ਰਹੇਗਾ।
How it works:
- ਇੱਕ ਉਮੀਦਵਾਰ (candidate) ਚੁਣੋ ਅਤੇ ਗਿਣਤੀ (count) ਨੂੰ 0 'ਤੇ ਸੈੱਟ ਕਰੋ।
- ਐਰੇ (array) ਵਿੱਚ ਲੂਪ ਚਲਾਓ।
- ਜੇਕਰ ਗਿਣਤੀ 0 ਹੈ, ਤਾਂ ਮੌਜੂਦਾ ਨੰਬਰ ਨੂੰ ਉਮੀਦਵਾਰ ਵਜੋਂ ਸੈੱਟ ਕਰੋ।
- ਜੇਕਰ ਮੌਜੂਦਾ ਨੰਬਰ ਉਮੀਦਵਾਰ ਨਾਲ ਮੇਲ ਖਾਂਦਾ ਹੈ, ਤਾਂ ਗਿਣਤੀ ਵਿੱਚ 1 ਵਾਧਾ ਕਰੋ।
- ਜੇਕਰ ਇਹ ਮੇਲ ਨਹੀਂ ਖਾਂਦਾ, ਤਾਂ ਗਿਣਤੀ ਵਿੱਚੋਂ 1 ਘਟਾਓ।
Complexity:
- Time: O(n) ਕਿਉਂਕਿ ਤੁਸੀਂ ਐਰੇ ਵਿੱਚੋਂ ਸਿਰਫ ਇੱਕ ਵਾਰ ਲੰਘਦੇ ਹੋ।
- Space: O(1) ਕਿਉਂਕਿ ਤੁਸੀਂ ਸਿਰਫ ਦੋ ਵੇਰੀਏਬਲਸ ਦੀ ਵਰਤੋਂ ਕਰਦੇ ਹੋ।
Why it matters:
ਦੋਵਾਂ ਵਿਧੀਆਂ ਦੀ Time Complexity O(n) ਹੈ। ਹਾਲਾਂਕਿ, ਦੂਜੀ ਪਹੁੰਚ ਬਹੁਤ ਘੱਟ ਮੈਮੋਰੀ ਦੀ ਵਰਤੋਂ ਕਰਦੀ ਹੈ। ਇਸਨੂੰ Map ਦੀ ਲੋੜ ਨਹੀਂ ਹੁੰਦੀ। ਇਹ ਇਸਨੂੰ ਵੱਡੇ ਡੇਟਾਸੈਟਾਂ (datasets) ਲਈ ਬਿਹਤਰ ਬਣਾਉਂਦਾ ਹੈ।
Source: https://dev.to/afuji/leetcode-150-day-4-majority-element-naive-vs-optimized-eo6