𝗟𝗲𝗲𝘁𝗰𝗼𝗱𝗲 𝟭𝟱𝟬 | 𝗗𝗮𝘆 𝟰: 𝗠𝗮𝗷𝗼𝗿𝗶𝘁𝘆 𝗘𝗹𝗲𝗺𝗲𝗻𝘁
Leetcode 169 તમને એક એરે (array) માં Majority Element શોધવાનું કહે છે. Majority Element n / 2 થી વધુ વખત દેખાય છે. આપણે માની લઈએ છીએ કે તે હંમેશા અસ્તિત્વ ધરાવે છે.
તમે આને બે રીતે ઉકેલી શકો છો.
અભિગમ 1: Map પદ્ધતિ
આ પદ્ધતિ દરેક સંખ્યા કેટલી વાર આવે છે તે ગણવા માટે Map નો ઉપયોગ કરે છે.
- કાઉન્ટ સ્ટોર કરવા માટે એક Map બનાવો.
- એરે (array) માં લૂપ ફેરવો.
- દરેક સંખ્યા માટે કાઉન્ટ અપડેટ કરો.
- n / 2 થી વધુ કાઉન્ટ ધરાવતી સંખ્યા શોધવા માટે Map માં લૂપ ફેરવો.
Complexity:
- Time: O(n) કારણ કે તમે બે ક્રમિક લૂપ્સનો ઉપયોગ કરો છો.
- Space: O(n) કારણ કે Map અનન્ય (unique) ઘટકોની સંખ્યા સાથે વધે છે.
અભિગમ 2: Boyer-Moore Voting Algorithm
આ કોન્સ્ટન્ટ મેમરીનો ઉપયોગ કરીને સમસ્યાને ઉકેલવાની એક ઓપ્ટિમાઇઝ્ડ રીત છે.
સંખ્યાઓને વિરોધી ટીમો તરીકે વિચારો. જ્યારે પણ એક સંખ્યા બીજી અલગ સંખ્યાને મળે છે, ત્યારે તેઓ એકબીજાને રદ (cancel) કરી દે છે. કારણ કે Majority Element અડધાથી વધુ વખત દેખાય છે, તેથી તે હંમેશા અંતમાં ટકી રહેશે.
તે કેવી રીતે કામ કરે છે:
- એક ઉમેદવાર (candidate) પસંદ કરો અને કાઉન્ટ 0 સેટ કરો.
- એરે (array) માં લૂપ ફેરવો.
- જો કાઉન્ટ 0 હોય, તો વર્તમાન સંખ્યાને ઉમેદવાર તરીકે સેટ કરો.
- જો વર્તમાન સંખ્યા ઉમેદવાર સાથે મેળ ખાતી હોય, તો કાઉન્ટમાં 1 ઉમેરો.
- જો તે મેળ ખાતી ન હોય, તો કાઉન્ટમાં 1 ઘટાડો.
Complexity:
- Time: O(n) કારણ કે તમે એરેમાંથી ફક્ત એક જ વાર પસાર થાઓ છો.
- Space: O(1) કારણ કે તમે ફક્ત બે વેરિયેબલ્સનો ઉપયોગ કરો છો.
તે શા માટે મહત્વનું છે:
બંને પદ્ધતિઓની ટાઈમ કોમ્પ્લેક્સિટી (time complexity) O(n) છે. જોકે, બીજો અભિગમ ઘણું ઓછું મેમરી વાપરે છે. તેને Map ની જરૂર નથી. આ તેને મોટા ડેટાસેટ્સ (datasets) માટે વધુ સારું બનાવે છે.
Source: https://dev.to/afuji/leetcode-150-day-4-majority-element-naive-vs-optimized-eo6