در این مطلب، ویدئو یافتن حداقل در آرایه مرتب شده چرخشی – جستجوی باینری – Leetcode 153 – پایتون با زیرنویس فارسی را برای دانلود قرار داده ام. شما میتوانید با پرداخت 15 هزار تومان ، این ویدیو به علاوه تمامی فیلم های سایت را دانلود کنید.اکثر فیلم های سایت به زبان انگلیسی می باشند. این ویدئو دارای زیرنویس فارسی ترجمه شده توسط هوش مصنوعی می باشد که میتوانید نمونه ای از آن را در قسمت پایانی این مطلب مشاهده کنید.
مدت زمان فیلم: 00:13:14
تصاویر این ویدئو:
قسمتی از زیرنویس این فیلم:
00:00:00,000 –> 00:00:02,080
سلام به همه خوش آمدید و بیایید
2
00:00:02,080 –> 00:00:04,240
امروز یک کد دقیق تر بنویسیم، بنابراین امروز
3
00:00:04,240 –> 00:00:05,520
بیایید مشکل
4
00:00:05,520 –> 00:00:09,519
پیدا کردن حداقل در یک آرایه مرتب شده چرخشی را حل
5
00:00:09,519 –> 00:00:12,719
کنیم، بنابراین یک آرایه ورودی به طول n به ما داده می شود
6
00:00:12,719 –> 00:00:16,239
که به ترتیب صعودی مرتب شده است
7
00:00:16,239 –> 00:00:19,520
اما می توان آن را یک تا
8
00:00:19,520 –> 00:00:22,720
n بار چرخاند. به عنوان مثال، اگر آرایهای
9
00:00:22,720 –> 00:00:23,119
مانند
10
00:00:23,119 –> 00:00:26,240
یک دو یک صفر و یک دو
11
00:00:26,240 –> 00:00:28,880
راست داشته باشیم تا آن را با یک بچرخانیم، اساساً
12
00:00:28,880 –> 00:00:30,960
به این معنی است که سمت راستترین عنصری را
13
00:00:30,960 –> 00:00:34,160
که میشناسید برداریم، آن را
14
00:00:34,160 –> 00:00:36,960
مانند این سمت راست به ابتدا منتقل کنیم، بنابراین
15
00:00:36,960 –> 00:00:37,360
16
00:00:37,360 –> 00:00:39,360
میتوانیم آن را با یک بچرخانیم. دو با
17
00:00:39,360 –> 00:00:41,680
گرفتن دو عنصر آخر
18
00:00:41,680 –> 00:00:44,079
و انتقال آنها به ابتدا، بنابراین
19
00:00:44,079 –> 00:00:45,120
چیزی شبیه به
20
00:00:45,120 –> 00:00:48,079
این به سمت راست دو تا چرخیده است
21
00:00:48,079 –> 00:00:48,879
و بنابراین
22
00:00:48,879 –> 00:00:52,079
میخواهیم حداقل مقدار را پیدا کنیم و
23
00:00:52,079 –> 00:00:53,520
میخواهیم این کار را در
24
00:00:53,520 –> 00:00:57,199
زمان log n انجام دهیم، همانطور که میگویند خوبی این است
25
00:00:57,199 –> 00:00:59,199
ما نوعی
26
00:00:59,199 –> 00:01:00,559
خاصیت مرتبسازی داریم که میتوانیم از
27
00:01:00,559 –> 00:01:01,199
آن
28
00:01:01,199 –> 00:01:04,239
برای یافتن راهحل زمان log n به نفع خود استفاده
29
00:01:04,239 –> 00:01:06,159
کنیم و تضمین میکنیم که هر مقدار
30
00:01:06,159 –> 00:01:08,400
در آرایه منحصر به فرد است
31
00:01:08,400 –> 00:01:10,320
، البته یافتن
32
00:01:10,320 –> 00:01:12,479
زمان خطی s آسان است. olution اساساً فقط
33
00:01:12,479 –> 00:01:13,119
34
00:01:13,119 –> 00:01:15,280
تمام مقادیر موجود در آرایه را اسکن کنید و
35
00:01:15,280 –> 00:01:17,439
سپس مقدار حداقل را بگیرید و آن را برگردانید،
36
00:01:17,439 –> 00:01:19,600
اما ما می توانیم از ویژگی مرتب سازی
37
00:01:19,600 –> 00:01:21,840
به نفع خود استفاده کنیم حتی اگر آرایه چرخانده شده باشد،
38
00:01:21,840 –> 00:01:23,840
اجازه دهید به شما نشان دهم چگونه می توانیم
39
00:01:23,840 –> 00:01:24,799
آن راه حل
40
00:01:24,799 –> 00:01:26,880
را انجام دهیم. بتوانید حدس بزنید
41
00:01:26,880 –> 00:01:28,080
که شامل
42
00:01:28,080 –> 00:01:30,640
الگوریتم جستجوی دودویی می شود که
43
00:01:30,640 –> 00:01:32,320
معمولاً الگوریتمی است که
44
00:01:32,320 –> 00:01:35,040
در گزارش و زمان اجرا می شود، بنابراین این واقعیت که
45
00:01:35,040 –> 00:01:36,960
آرایه در ابتدا مرتب شده است چیزی است که
46
00:01:36,960 –> 00:01:38,880
به شما اشاره می کند که جستجوی باینری ممکن
47
00:01:38,880 –> 00:01:40,000
است در این مورد کار کند، اما
48
00:01:40,000 –> 00:01:41,520
انجام نمی شود. اکنون که یک
49
00:01:41,520 –> 00:01:43,119
جستجوی باینری سنتی باشد، البته
50
00:01:43,119 –> 00:01:46,000
اگر کل آرایه مرتب شده باشد،
51
00:01:46,000 –> 00:01:46,720
52
00:01:46,720 –> 00:01:48,960
n بار چرخیده است، این اساساً به این معنی است که ما یک آر
53
00:01:48,960 –> 00:01:51,200
یه مرتب شده را انتخاب کردیم، مانند یک دو سه چهار پن
54
00:01:51,200 –> 00:01:52,960
، آن را n بار چرخانده ایم، اس
55
00:01:52,960 –> 00:01:54,960
ساً اکنون آن را به ترتیب مرتب شده اصلی گذاشته ای
56
00:01:54,960 –> 00:01:57,200
. آرایهای داشتیم که
57
00:01:57,200 –> 00:01:57,680
58
00:01:57,680 –> 00:02:00,000
کاملاً مانند این مرتب شده بود، یک
59
00:02:00,000 –> 00:02:02,000
جستجوی دودویی آسان روی یک آرایه مرتبشده کار میکرد،
60
00:02:02,000 –> 00:02:02,640
اما
61
00:02:02,640 –> 00:02:04,640
اگر آرایه کاملا مرتب شده باشد،
62
00:02:04,640 –> 00:02:06,399
میدانیم که حداقل مقدار سمت
63
00:02:06,399 –> 00:02:08,800
چپ خواهد بود. به سمت راست بروید، بنابراین اگر در هر نقطه ای
64
00:02:08,800 –> 00:02:11,520
به یک جستجوی باینری رسیدیم، می دانید که
65
00:02:11,520 –> 00:02:13,280
می دانید یک نشانگر چپ و یک
66
00:02:13,280 –> 00:02:14,720
اشاره گر راست اگر
67
00:02:14,720 –> 00:02:17,360
به نقطه ای رسیدیم که کل آرایه
68
00:02:17,360 –> 00:02:19,360
مرتب شده است، می توانیم فقط چپ ترین
69
00:02:19,360 –> 00:02:21,280
عنصر یا حداقل را برگردانیم. این را به
70
00:02:21,280 –> 00:02:23,120
عنوان حداقل مقدار در نظر بگیرید،
71
00:02:23,120 –> 00:02:25,760
بنابراین بیایید یک جستجوی باینری را امتحان کنیم و ببینیم که چگونه
72
00:02:25,760 –> 00:02:26,640
73
00:02:26,640 –> 00:02:29,520
با یک جستجوی باینری معمولی متفاوت خواهد بود
74
00:02:29,520 –> 00:02:30,400
، البته
75
00:02:30,400 –> 00:02:32,800
ما میخواهیم حداقل مقداری را
76
00:02:32,800 –> 00:02:34,239
که میخواهیم نشانگر چپ و اشارهگر سمت راست خود را مقداردهی اولیه کنیم، پیدا
77
00:02:34,239 –> 00:02:35,440
کنیم. در اینجا
78
00:02:35,440 –> 00:02:36,319
اساساً
79
00:02:36,319 –> 00:02:38,400
وضعیت اشاره گر فعلی به این معنی است که
80
00:02:38,400 –> 00:02:40,879
ما کل این آرایه را در نظر می گیریم
81
00:02:40,879 –> 00:02:43,120
تا حداقل حداقلی را که می تواند
82
00:02:43,120 –> 00:02:44,640
از هر نقطه از این
83
00:02:44,640 –> 00:02:47,440
آرایه باشد و نتیجه
84
00:02:47,440 –> 00:02:48,000
حداقل خواهد بود
85
00:02:48,000 –> 00:02:49,599
و من اکنون آن را در
86
00:02:49,599 –> 00:02:52,000
اینجا دنبال می کنم. البته یکی از راههایی که میتوانیم این مشکل را انجام دهیم
87
00:02:52,000 –> 00:02:54,319
این است که اساساً نقطه محوری را به
88
00:02:54,319 –> 00:02:56,080
سمت راست پیدا کنیم، موقعیتی را پیدا کنیم که در
89
00:02:56,080 –> 00:02:59,000
آن میدانی عناصر به
90
00:02:59,000 –> 00:03:00,959
ترتیب
91
00:03:00,959 –> 00:03:03,120
از اینجا به اینجا افزایش نمییابند، سه تا چهار آنها
92
00:03:03,120 –> 00:03:04,879
به ترتیب افزایشی هستند. از چهار به پنج در
93
00:03:04,879 –> 00:03:05,280
آنجا
94
00:03:05,280 –> 00:03:07,440
به ترتیب افزایش از یک به
95
00:03:07,440 –> 00:03:08,480
دو هستند، آنها همچنین
96
00:03:08,480 –> 00:03:10,879
به ترتیب افزایش مییابند، اما از پنج به یک
97
00:03:10,879 –> 00:03:12,640
به ترتیب کاهشی هستند، این نقطه
98
00:03:12,640 –> 00:03:14,879
محوری سمت راست است، بنابراین اساساً این مقدار
99
00:03:14,879 –> 00:03:16,319
حداقل خواهد بود، اما من. میخواهم این
100
00:03:16,319 –> 00:03:17,680
کار را به روشی متفاوت
101
00:03:17,680 –> 00:03:19,440
انجام دهم، جایی که لزوماً مجبور نیستیم
102
00:03:19,440 –> 00:03:21,519
بدانیم دقیقاً به دنبال محور بگردید، من
103
00:03:21,519 –> 00:03:22,720
میخواهم خوب را به سمت چپ ببرم
104
00:03:22,720 –> 00:03:24,959
، نیمی از آنها را بگیرید
105
00:03:24,959 –> 00:03:26,400
نشانگر وسط ما را دریافت کنید وسط ما
106
00:03:26,400 –> 00:03:27,280
تمام میشود. در اینجا در
107
00:03:27,280 –> 00:03:30,000
5. بنابراین من 5
108
00:03:30,000 –> 00:03:32,000
را حداقل مقداری که تا به حال دیدهایم در نظر
109
00:03:32,000 –> 00:03:33,920
میگیرم، بنابراین نتیجه ما پنج خواهد شد
110
00:03:33,920 –> 00:03:35,519
111
00:03:35,519 –> 00:03:38,239
اکنون باید از خود بپرسیم خوب
112
00:03:38,239 –> 00:03:39,840
میدانید که این میتوانست نتیجه باشد، اما
113
00:03:39,840 –> 00:03:40,239
اکنون
114
00:03:40,239 –> 00:03:41,840
ما نمی خواهم بدانید
115
00:03:41,840 –> 00:03:43,680
دوباره به این مقدار نگاه کنید، بنابراین این سوال پیش می آید که آیا
116
00:03:43,680 –> 00:03:45,680
ما به سمت چپ جستجو می کنیم یا
117
00:03:45,680 –> 00:03:46,879
به سمت راست جستجو
118
00:03:46,879 –> 00:03:48,799
می کنیم که در کجا حداقل
119
00:03:48,799 –> 00:03:50,720
مقدار را پیدا کنیم.
120
00:03:50,720 –> 00:03:52,000
این حتی کوچکتر از
121
00:03:52,000 –> 00:03:55,200
5 است. خوب ابتدا این را از زمانی که چرخانده ایم در نظر بگیرید
122
00:03:55,200 –> 00:03:56,720
آرایه ما
123
00:03:56,720 –> 00:03:58,640
دو قسمت از آرایه داریم که به
124
00:03:58,640 –> 00:04:00,640
سمت راست مرتب شده اند ما این قسمت
125
00:04:00,640 –> 00:04:02,879
از آرایه را داریم که قسمت چپ
126
00:04:02,879 –> 00:04:03,760
127
00:04:03,760 –> 00:04:05,760
را به راست مرتب می کند و قسمت مرتب شده سمت راست
128
00:04:05,760 –> 00:04:07,120
آرایه را داریم که
129
00:04:07,120 –> 00:04:10,159
مرتب شده است بنابراین سوال برای ما با
130
00:04:10,159 –> 00:04:11,760
این نشانگر وسط است.
131
00:04:11,760 –> 00:04:14,879
در این مقدار 5 آیا ما در حال حاضر در
132
00:04:14,879 –> 00:04:17,440
قسمت مرتب شده سمت چپ هستیم یا در حال
133
00:04:17,440 –> 00:04:18,079
134
00:04:18,079 –> 00:04:21,120
حاضر در قسمت مرتب شده سمت راست هستیم اگر
135
00:04:21,120 –> 00:04:21,358
136
00:04:21,358 –> 00:04:23,919
در قسمت مرتب شده چپ آرایه هستیم
137
00:04:23,919 –> 00:04:26,479
آیا نمی خواهیم قسمت مرتب شده سمت راست را جستجو کنیم
138
00:04:26,479 –> 00:04:27,199
139
00:04:27,199 –> 00:04:30,000
دلیل اینکه آیا مرتب سازی شده است اگر
140
00:04:30,000 –> 00:04:31,280
آرایه را بچرخانیم،
141
00:04:31,280 –> 00:04:34,400
قسمت چپ همیشه
142
00:04:34,400 –> 00:04:37,680
مقادیری دارد که از هر مقدار
143
00:04:37,680 –> 00:04:38,080
در
144
00:04:38,080 –> 00:04:40,400
قسمت راست مرتب شده است، زیرا وقتی
145
00:04:40,400 –> 00:04:42,400
به راست میچرخانیم، فرض کنید آرایهای مانند
146
00:04:42,400 –> 00:04:43,520
147
00:04:43,520 –> 00:04:45,759
این، راستترین مقدار را بزرگترین
148
00:04:45,759 –> 00:04:47,840
مقدار میگیریم و آن را قرار میدهیم. در اینجا سمت راست، بنابراین
149
00:04:47,840 –> 00:04:48,639
ما
150
00:04:48,639 –> 00:04:51,360
مقادیر بزرگتر را می گیریم و آنها را در سمت چپ و
151
00:04:51,360 –> 00:04:51,919
152
00:04:51,919 –> 00:04:53,759
راست قرار می دهیم، بنابراین مقادیر
153
00:04:53,759 –> 00:04:56,080
سمت راست اکنون کوچکتر می شوند،
154
00:04:56,080 –> 00:04:57,520
بنابراین به همین دلیل است که همیشه
155
00:04:57,520 –> 00:05:00,160
همینطور خواهد بود، بنابراین اگر o اشاره گر وسط ur در
156
00:05:00,160 –> 00:05:01,039
حال حاضر
157
00:05:01,039 –> 00:05:03,520
در مقداری است که در قسمت مرتب شده سمت چپ است،
158
00:05:03,520 –> 00:05:04,160
159
00:05:04,160 –> 00:05:06,080
سپس می خواهیم قسمت مرتب شده سمت راست را جستجو کنیم
160
00:05:06,080 –> 00:05:08,160
زیرا مقادیر کوچک تری
161
00:05:08,160 –> 00:05:11,280
در سمت راست دارد، بنابراین چگونه می توانیم بدانیم که آیا
162
00:05:11,280 –> 00:05:11,600
در
163
00:05:11,600 –> 00:05:14,880
قسمت مرتب شده سمت چپ به خوبی همانطور که گفتم
164
00:05:14,880 –> 00:05:16,960
هر مقدار هستیم، هستیم. در قسمت مرتب شده سمت راست
165
00:05:16,960 –> 00:05:19,120
کوچکتر از هر مقدار
166
00:05:19,120 –> 00:05:20,560
در قسمت مرتب شده سمت چپ خواهد بود،
167
00:05:20,560 –> 00:05:23,440
بنابراین یک چیزی که می توانیم بررسی کنیم این است که آیا
168
00:05:23,440 –> 00:05:24,080
169
00:05:24,080 –> 00:05:27,440
مقدار وسط فعلی بزرگتر یا
170
00:05:27,440 –> 00:05:30,720
برابر با مقدار در
171
00:05:30,720 –> 00:05:34,160
سمت چپ چیز ما در سمت راست است، زیرا
172
00:05:34,160 –> 00:05:35,440
173
00:05:35,440 –> 00:05:38,400
اگر مقدار وسط
174
00:05:38,400 –> 00:05:40,800
بزرگتر یا مساوی با سمت چپ
175
00:05:40,800 –> 00:05:41,440
باشد، مقدار سمت چپ کوچکترین مقدار خواهد بود،
176
00:05:41,440 –> 00:05:44,560
به این معنی که این مقدار میانی بخشی
177
00:05:44,560 –> 00:05:47,600
از این بخش مرتبسازی شده سمت چپ است، در
178
00:05:47,600 –> 00:05:49,280
این صورت میخواهیم
179
00:05:49,280 –> 00:05:51,520
اگر وسط خود را به سمت راست جستجو کنیم. نشانگر
180
00:05:51,520 –> 00:05:53,280
فرض کنید در این مورد میتوانیم ببینیم
181
00:05:53,280 –> 00:05:56,000
پنج بزرگتر یا مساوی سه است
182
00:05:56,000 –> 00:05:56,479
،
183
00:05:56,479 –> 00:05:58,160
دلیل اینکه ما بزرگتر یا مساوی میکنیم این
184
00:05:58,160 –> 00:05:59,919
است که این نشانگر وسط
185
00:05:59,919 –> 00:06:01,919
میتواند در واقع در سمت چپ باشد
186
00:06:01,919 –> 00:06:03,600
و همچنین یک لبه است.
187
00:06:03,600 –> 00:06:05,919
در این مورد و در آن صورت ما همچنین می دانید که
188
00:06:05,919 –> 00:06:07,680
این قسمت مرتب شده سمت چپ خواهد بود،
189
00:06:07,680 –> 00:06:10,000
اما فرض کنید نشانگر وسط ما به
190
00:06:10,000 –> 00:06:10,800
جای اینکه در
191
00:06:10,800 –> 00:06:13,840
5 باشد، در اینجا به پایان رسیده است، در این حالت در
192
00:06:13,840 –> 00:06:16,800
یک وضعیت ما به
193
00:06:16,800 –> 00:06:18,319
آن بی حسی وسط ارزیابی
194
00:06:18,319 –> 00:06:20,240
می شود. بزرگتر یا
195
00:06:20,240 –> 00:06:21,919
مساوی مقدار سمت چپ
196
00:06:21,919 –> 00:06:24,400
که سه است درست نیست
197
00:06:24,400 –> 00:06:26,400
زیرا مقادیر این قسمت مرتب شده سمت راست
198
00:06:26,400 –> 00:06:26,960
199
00:06:26,960 –> 00:06:29,440
کوچکتر از قسمت مرتب شده سمت چپ خواهد بود در
200
00:06:29,440 –> 00:06:31,360
این صورت
201
00:06:31,360 –> 00:06:34,400
اگر نادرست باشد به سمت راست نادرست ارزیابی می شود، به این معنی که می
202
00:06:34,400 –> 00:06:36,160
دانید آیا ما ‘در یک مقدار است که
203
00:06:36,160 –> 00:06:38,639
در قسمت مرتب شده سمت راست است، سپس می خواهیم
204
00:06:38,639 –> 00:06:39,360
205
00:06:39,360 –> 00:06:41,919
به سمت چپ راست جستجو کنیم زیرا در این
206
00:06:41,919 –> 00:06:42,479
207
00:06:42,479 –> 00:06:44,800
مورد اگر وسط ما در این بود، سمت راست
208
00:06:44,800 –> 00:06:46,479
منطقی است که
209
00:06:46,479 –> 00:06:48,240
شما می دانید همه مقادیر سمت راست
210
00:06:48,240 –> 00:06:49,919
آن هستند. بزرگتر خواهد شد
211
00:06:49,919 –> 00:06:51,599
، پس ما می خواهیم به سمت چپ جستجو کنیم،
212
00:06:51,599 –> 00:06:53,680
اما بدیهی است که این مقادیر نیز
213
00:06:53,680 –> 00:06:54,800
بزرگتر هستند، اما
214
00:06:54,800 –> 00:06:56,160
این موضوع این موضوع را نشان نمی دهد،
215
00:06:56,160 –> 00:06:57,520
زیرا اگر نشانگر وسط ما
216
00:06:57,52