در این مطلب، ویدئو تمرین برنامه نویسی پایتون: LeetCode #169 — Majority Element با زیرنویس فارسی را برای دانلود قرار داده ام. شما میتوانید با پرداخت 15 هزار تومان ، این ویدیو به علاوه تمامی فیلم های سایت را دانلود کنید.اکثر فیلم های سایت به زبان انگلیسی می باشند. این ویدئو دارای زیرنویس فارسی ترجمه شده توسط هوش مصنوعی می باشد که میتوانید نمونه ای از آن را در قسمت پایانی این مطلب مشاهده کنید.
مدت زمان فیلم: 00:10:40
تصاویر این ویدئو:
قسمتی از زیرنویس این فیلم:
00:00:02,000 –> 00:00:04,480
سلام به همه و به
2
00:00:04,480 –> 00:00:06,160
تمرین برنامه نویسی پایتون
3
00:00:06,160 –> 00:00:07,600
در این قسمت خوش آمدید، ما قصد داریم به
4
00:00:07,600 –> 00:00:10,240
کد نخبگان شماره 169
5
00:00:10,240 –> 00:00:13,280
6
00:00:13,280 –> 00:00:16,320
7
00:00:16,320 –> 00:00:18,080
8
00:00:18,080 –> 00:00:21,119
9
00:00:21,119 –> 00:00:23,760
عنصر اکثریت بپردازیم. عنصر اکثریت
10
00:00:23,760 –> 00:00:24,480
11
00:00:24,480 –> 00:00:28,000
عنصری است که بیشتر از
12
00:00:28,000 –> 00:00:30,400
n تقسیم بر دو برابر ظاهر می شود، بنابراین
13
00:00:30,400 –> 00:00:31,199
بیش
14
00:00:31,199 –> 00:00:34,880
از نیمی از زمان اندازه
15
00:00:34,880 –> 00:00:37,840
آرایه ظاهر می شود، ممکن است فرض کنید که آرایه
16
00:00:37,840 –> 00:00:38,160
17
00:00:38,160 –> 00:00:40,879
خالی نیست و عنصر اکثریت
18
00:00:40,879 –> 00:00:42,960
همیشه در آرایه وجود دارد. بنابراین قرار
19
00:00:42,960 –> 00:00:44,640
نیست آرایهای به ما داده شود
20
00:00:44,640 –> 00:00:46,480
که عنصر اکثریت
21
00:00:46,480 –> 00:00:47,280
22
00:00:47,280 –> 00:00:49,760
نداشته باشد، همیشه چیزی وجود خواهد داشت
23
00:00:49,760 –> 00:00:51,440
که پاسخ صحیح است
24
00:00:51,440 –> 00:00:53,039
و ما در اینجا چند مثال به
25
00:00:53,039 –> 00:00:55,440
ما داده میشود، ما یک لیست
26
00:00:55,440 –> 00:00:58,960
از 3 تا 3 داریم. 2 3 در آن
27
00:00:58,960 –> 00:01:01,199
و عنصر اکثریت در اینجا 3 است
28
00:01:01,199 –> 00:01:02,000
زیرا
29
00:01:02,000 –> 00:01:05,600
3 بیشتر از n تقسیم بر 2 برابر ظاهر می شود
30
00:01:05,600 –> 00:01:06,799
بنابراین در این
31
00:01:06,799 –> 00:01:09,600
مورد طول لیست 3 است و تقسیم بر 2
32
00:01:09,600 –> 00:01:11,200
1 و نیم خواهد بود
33
00:01:11,200 –> 00:01:14,000
بنابراین سه بیشتر از یک و
34
00:01:14,000 –> 00:01:16,320
نیم برابر ظاهر می شود. ظاهر می شود دو بار
35
00:01:16,320 –> 00:01:18,479
و در مثال دوم ما دو
36
00:01:18,479 –> 00:01:19,360
دو
37
00:01:19,360 –> 00:01:21,759
سه یک و سپس دو دو داریم بنابراین در این
38
00:01:21,759 –> 00:01:23,600
مورد یک آرایه از طول داریم که
39
00:01:23,600 –> 00:01:24,159
این
40
00:01:24,159 –> 00:01:29,360
هفت است و 7 تقسیم بر 2 یعنی 3.5
41
00:01:29,360 –> 00:01:30,880
بنابراین باید عنصری را پیدا کنیم
42
00:01:30,880 –> 00:01:33,520
که بیشتر از 3.5 بار
43
00:01:33,520 –> 00:01:37,200
و در این مورد 2 1 2 3 4 بار ظاهر می شود،
44
00:01:37,200 –> 00:01:39,360
بنابراین عنصر اکثریت در این
45
00:01:39,360 –> 00:01:40,320
مورد است،
46
00:01:40,320 –> 00:01:41,920
بنابراین برای فکر کردن به این مشکل،
47
00:01:41,920 –> 00:01:44,240
به ویرایشگر کد می
48
00:01:44,240 –> 00:01:45,920
رویم، اما ابتدا
49
00:01:45,920 –> 00:01:48,720
تخته سفید خود را بررسی می کنیم و می نویسیم که چگونه ما
50
00:01:48,720 –> 00:01:51,360
ممکن است بتوانیم به این مشکل نزدیک شویم،
51
00:01:51,360 –> 00:01:53,600
بنابراین با توجه به ساختار این مشکل،
52
00:01:53,600 –> 00:01:54,479
53
00:01:54,479 –> 00:01:56,240
اساساً فقط یک آرایه به ما داده می شود و
54
00:01:56,240 –> 00:01:57,600
باید
55
00:01:57,600 –> 00:02:00,479
هر عنصری را که بیشتر
56
00:02:00,479 –> 00:02:00,960
57
00:02:00,960 –> 00:02:03,040
اتفاق می افتد پیدا کنیم، اتفاقاً عنصری که
58
00:02:03,040 –> 00:02:04,320
اغلب رخ می دهد
59
00:02:04,320 –> 00:02:07,759
نیز در حداقل یا بیشتر از n
60
00:02:07,759 –> 00:02:09,199
به دو صورت تقسیم می شود،
61
00:02:09,199 –> 00:02:11,120
اما اصل مشکل این است که ما
62
00:02:11,120 –> 00:02:12,319
هر عنصری را
63
00:02:12,319 –> 00:02:15,680
می یابیم که در اکثر مواقع یا
64
00:02:15,680 –> 00:02:18,239
بیش از نیمی از مواقع
65
00:02:18,239 –> 00:02:20,800
ظاهر می شود، همان عنصری است که اغلب ظاهر می شود،
66
00:02:20,800 –> 00:02:22,400
بنابراین برای این دنباله من فقط خویشاوندان d از ثبت
67
00:02:22,400 –> 00:02:24,080
تصادفی در اینجا
68
00:02:24,080 –> 00:02:26,480
عنصر اکثریت 2 خواهد بود، هم
69
00:02:26,480 –> 00:02:27,520
به این دلیل که
70
00:02:27,520 –> 00:02:31,120
2 بیشترین دفعات را نشان می دهد و هم به دلیل اینکه 2
71
00:02:31,120 –> 00:02:34,239
حداقل n تقسیم بر 2 برابر رخ می دهد در
72
00:02:34,239 –> 00:02:36,720
این مورد این آرایه ای به طول
73
00:02:36,720 –> 00:02:40,560
هفت است، بنابراین بیشتر از
74
00:02:40,560 –> 00:02:43,280
هفت تقسیم بر دو رخ می دهد. یا سه نقطه پنج
75
00:02:43,280 –> 00:02:45,200
بار چهار بار اتفاق میافتد،
76
00:02:45,200 –> 00:02:48,000
اما چگونه میتوانیم به خوبی پیدا کنیم که
77
00:02:48,000 –> 00:02:50,000
عنصر اکثریت در کد چیست
78
00:02:50,000 –> 00:02:52,000
که به نظر میرسد چندان
79
00:02:52,000 –> 00:02:54,480
دشوار نباشد، تنها کاری که واقعاً باید انجام دهیم این
80
00:02:54,480 –> 00:02:57,680
است که هر عنصر را ردیابی کنیم
81
00:02:57,680 –> 00:03:00,319
و حساب کنیم که چگونه بارها
82
00:03:00,319 –> 00:03:01,200
ظاهر می
83
00:03:01,200 –> 00:03:03,200
شوند، به عنوان مثال ما می توانیم
84
00:03:03,200 –> 00:03:04,560
از طریق این آرایه حلقه بزنیم
85
00:03:04,560 –> 00:03:06,879
و بگوییم خیلی خوب اولین چیزی است که دو است
86
00:03:06,879 –> 00:03:07,760
و اکنون ما
87
00:03:07,760 –> 00:03:10,879
دو را یک بار دیده ایم که عنصر بعدی دو است، بنابراین
88
00:03:10,879 –> 00:03:11,840
اکنون دو دو بار مشاهده کرده ایم که
89
00:03:11,840 –> 00:03:14,560
عنصر بعدی است. یکی پس حالا
90
00:03:14,560 –> 00:03:15,440
91
00:03:15,440 –> 00:03:16,959
یک بار یک بار دیده ایم و فقط همینطور ادامه می
92
00:03:16,959 –> 00:03:18,959
دهیم دوباره دو را می بینیم بنابراین تکرار می کنیم که
93
00:03:18,959 –> 00:03:19,680
تا سه
94
00:03:19,680 –> 00:03:22,400
یک سه را می بینیم بنابراین این یک چیز جدید است و
95
00:03:22,400 –> 00:03:24,319
در یک نقطه از کل
96
00:03:24,319 –> 00:03:25,040
آرایه عبور می کنیم
97
00:03:25,040 –> 00:03:27,680
و سپس می توانیم با فهرست یا
98
00:03:27,680 –> 00:03:29,519
فرهنگ لغت باقی مانده است که ممکن است از f استفاده کنیم یا این در
99
00:03:29,519 –> 00:03:30,400
پایتون
100
00:03:30,400 –> 00:03:33,519
که نشان میدهد هر مقداری که وجود دارد
101
00:03:33,519 –> 00:03:36,000
چند بار رخ میدهد و سپس میتوانیم
102
00:03:36,000 –> 00:03:36,879
103
00:03:36,879 –> 00:03:39,440
هر مقدار حداکثری را از آن استخراج کنیم
104
00:03:39,440 –> 00:03:39,920
105
00:03:39,920 –> 00:03:42,239
و برگردانیم که به عنوان پاسخ و یک
106
00:03:42,239 –> 00:03:44,080
بینش دیگر که در اینجا میتوانیم داشته باشیم، در واقع
107
00:03:44,080 –> 00:03:44,400
به
108
00:03:44,400 –> 00:03:47,280
آن نیازی نداریم. برای اینکه
109
00:03:47,280 –> 00:03:47,840
110
00:03:47,840 –> 00:03:49,760
111
00:03:49,760 –> 00:03:50,879
112
00:03:50,879 –> 00:03:53,120
هر بار که میخواهیم چیزی را
113
00:03:53,120 –> 00:03:54,159
114
00:03:54,159 –> 00:03:56,560
در این فرهنگ لغت که میسازیم ذخیره کنیم، لزوماً صبر کنیم تا به پایان برسیم تا مقدار نهایی را بیرون بیاوریم، میتوانیم
115
00:03:56,560 –> 00:03:57,360
116
00:03:57,360 –> 00:04:00,239
در آن نقطه بررسی کنیم که آیا مقدار در آنجا
117
00:04:00,239 –> 00:04:02,640
بزرگتر از n است تقسیم بر دو در حال حاضر،
118
00:04:02,640 –> 00:04:04,879
زیرا اگر قبلاً بیش از n
119
00:04:04,879 –> 00:04:06,239
تقسیم بر دو ورودی در آنجا داشته باشیم،
120
00:04:06,239 –> 00:04:07,840
عنصر اکثریت است و
121
00:04:07,840 –> 00:04:09,840
نیازی نیست که
122
00:04:09,840 –> 00:04:11,599
در بقیه آرایه حلقه بزنیم، فقط می توانیم
123
00:04:11,599 –> 00:04:13,120
پاسخ را در آن نقطه برگردانیم،
124
00:04:13,120 –> 00:04:15,680
بنابراین بیایید پرش کنیم. به ویرایشگر کد بازگردید
125
00:04:15,680 –> 00:04:17,680
و ببینید چگونه میتوانیم این راهحل را کدنویسی
126
00:04:17,680 –> 00:04:18,880
کنیم،
127
00:04:18,880 –> 00:04:21,199
بنابراین اساساً آنچه در اینجا میخواهیم انجام دهیم
128
00:04:21,199 –> 00:04:22,000
این
129
00:04:22,000 –> 00:04:25,440
است که یک فرهنگ لغت ایجاد کنیم که
130
00:04:25,440 –> 00:04:25,919
از طریق
131
00:04:25,919 –> 00:04:28,400
هر عنصری که به ما داده میشود حلقه بزند، بنابراین
132
00:04:28,400 –> 00:04:30,639
فهرستی از شمارههایی
133
00:04:30,639 –> 00:04:34,800
که میخواهیم به ما داده شود. که بخواهد بقیه را ذخیره کند
134
00:04:34,800 –> 00:04:36,800
در یک فرهنگ لغت قرار می گیرد، بنابراین ما یک
135
00:04:36,800 –> 00:04:39,040
فرهنگ لغت خالی در اینجا ایجاد می
136
00:04:39,040 –> 00:04:41,840
کنیم و سپس فقط روی اعداد حلقه می زنیم،
137
00:04:41,840 –> 00:04:42,320
بنابراین
138
00:04:42,320 –> 00:04:46,160
برای n در nums
139
00:04:46,160 –> 00:04:49,120
، ابتدا می توانیم بررسی کنیم که آیا n در حال حاضر
140
00:04:49,120 –> 00:04:50,479
در فرهنگ لغت جمع وجود دارد،
141
00:04:50,479 –> 00:04:52,400
اگر نیست، باید آن را اضافه کنیم.
142
00:04:52,400 –> 00:04:54,560
آن را به مقدار یک مقداردهی اولیه کنید،
143
00:04:54,560 –> 00:04:57,680
بنابراین اگر n
144
00:04:57,680 –> 00:05:01,039
به صورت مجموع نباشد، اگر با مجموع نیست،
145
00:05:01,039 –> 00:05:04,560
آن را اضافه می کنیم زیرا مجموع n
146
00:05:04,560 –> 00:05:06,400
در ابتدا برابر با یک خواهد بود، به این معنی
147
00:05:06,400 –> 00:05:08,720
که تا کنون فقط یک بار آن عدد را دیده ایم
148
00:05:08,720 –> 00:05:11,759
و اگر قبلاً به صورت مجموع بوده است. خوب
149
00:05:11,759 –> 00:05: