Quick Sort шиг хуваагаад зөвхөн нэг талыг нь үргэлжлүүлж, k дахь хамгийн бага тоог олно.

IntermediateХугацаа: Дунджаар O(n), муу үед O(n²)Санах ой: O(1)
HackerRank дээр бодох Өөр алгоритмтай уралдуулах

Эхлээд жижиг бодлого

a = [7, 2, 9, 4, 1, 8, 3] дотроос 4 дэх хамгийн бага тоог олъё. Эрэмбэлбэл [1, 2, 3, 4, 7, 8, 9] болох тул хариу 4.

Quickselect бүгдийг эрэмбэлэхгүй. Хуваалт бүрийн дараа хариу байгаа талаа л үргэлжлүүлнэ.

Энгийн аргаас санаа руу

Энгийн арга: sort хийгээд a[k - 1] утгыг авна. O(n log n). Ихэнх ажил дэмий: бусад тоонуудын дарааллыг мэдэх хэрэггүй.

Гол санаа: Quick Sort-ын хуваалтыг хийнэ. Pivot-оос бага тоонууд зүүн тийш, бусад нь баруун тийш очно. Pivot-ын эзэлсэн байр i бол түүний эрэмбэлсэн байр. i = k бол оллоо. i < k бол хариу баруун талд, үгүй бол зүүн талд. Нөгөө талыг огт оролдохгүй.

Нэр томьёо ба тэмдэглэгээ

pivot
Хуваалтын төв болох тоо. Энэ кодод хэсгийн сүүлийн тоо.
k
0-ээс эхэлсэн байр. Код эхэндээ k-- хийнэ.
Lomuto хуваалт
j-г зүүнээс баруун тийш гүйлгэж, pivot-оос бага тоог i байранд шилжүүлдэг хуваалт.
nth_element
C++-ийн ижил ажил хийдэг function: nth_element(a, a + k, a + n).
k = 3

4 дэх хамгийн бага тоог олъё. Array-г эрэмбэлбэл энэ тоо a[3] байранд очно. Бүгдийг эрэмбэлэхгүй: Quick Sort шиг хуваагаад, k байгаа талаа л үргэлжлүүлнэ.

Алхам 1 / 34
Хурд
  • Энгийн
  • Pivot (p)
  • p-тэй харьцуулж буй
  • Солигдсон
  • Байрандаа орсон
  • k дахь хамгийн бага
  • Хайхаа больсон хэсэг
Слайд 1 / 6

k дахь хамгийн бага

7 тооны 4 дэх хамгийн бага нь хэд вэ? Бүгдийг эрэмбэлж болно, гэхдээ илүү ажил их. Quick Sort шиг хуваагаад, зөвхөн нэг талыг нь үргэлжлүүлье.

quickselect.cpp
#include <bits/stdc++.h>
using namespace std;
int n, k, a[100005];
int main() {
cin >> n >> k;
for (int i = 0; i < n; i++) cin >> a[i];
k--;
int l = 0, r = n - 1;
while (l < r) {
int p = a[r], i = l;
for (int j = l; j < r; j++) {
if (a[j] < p) {
swap(a[i], a[j]);
i++;
}
}
swap(a[i], a[r]);
if (i == k) {
break;
}
if (i < k) {
l = i + 1;
} else {
r = i - 1;
}
}
cout << a[k] << '\n';
return 0;
}

Юунд хэрэгтэй вэ?

Медиан эсвэл k дахь хамгийн бага тоог бүх array-г эрэмбэлэхгүйгээр дунджаар n орчим алхамд олно. C++-ийн nth_element ижил санаатай.

Яаж ажилладаг вэ?

1. [l, r] хэсгийн сүүлийн тоо pivot p болно. 2. Pivot-оос бага тоонуудыг зүүн тийш гаргаад, pivot-ыг тэдний ард тавина. Одоо pivot эрэмбэлсэн байрандаа буюу i-р байранд байна. 3. i = k бол хариу олдлоо. 4. i < k бол зөвхөн баруун хэсгийг (l = i + 1), үгүй бол зөвхөн зүүн хэсгийг (r = i − 1) үргэлжлүүлнэ. Эрэмбэлэгдсэн array дээр удаан ажиллана (n²). Pivot-ыг санамсаргүй сонговол энэ бараг гардаггүй. Оролт: n, k, дараа нь n тоо.

Яагаад зөв, хэр хурдан бэ?

Хуваалтын дараа pivot-оос зүүн талын бүх тоо түүнээс бага, баруун талынх нь их буюу тэнцүү. Тиймээс pivot эрэмбэлсэн array-д яг i-р байранд очно. k-р байрны тоо i < k бол заавал баруун хэсэгт, i > k бол зүүн хэсэгт байна.

Pivot ихэвчлэн дунд хавьцаа буудаг тул хэсэг дунджаар хоёр дахин багасна: n + n/2 + n/4 + … ≈ 2n. Хамгийн муудаа, эрэмбэлэгдсэн array дээр n²/2. n = 10⁵ бол 5 тэрбум алхам болж хэт удаан.

Түгээмэл алдаа

  • k-г 1-ээс эхэлсэн дугаараар нь ашиглах. Код k-- хийж 0-ээс эхэлсэн байр болгодог.
  • Эрэмбэлэгдсэн эсвэл ижил тоо ихтэй array дээр сүүлийн тоог pivot болгох нь n² хугацаа авна. Pivot-ыг санамсаргүй сонгоод сүүлийн байранд зөө.
  • Хуваалтын дараа pivot-ыг a[i] байранд солихоо мартах. Тэгвэл i нь pivot-ын байр биш болно.
  • Анхны дарааллыг хадгалах хэрэгтэй бол хуулбар дээр ажилла. Quickselect array-г өөрчилдөг.

Хязгаарын тохиолдол

  • k = 1: хамгийн бага тоо. k = n: хамгийн их тоо.
  • Бүх тоо ижил: a[j] < p хэзээ ч үнэн биш, pivot зүүн зах руу очно. Хариу зөв, гэхдээ n² хугацаа.
  • n = 1: loop огт эргэхгүй, хариу a[0].

Өөрийгөө шалга

  1. a = [5, 1, 4] дээр эхний хуваалтын дараа array ямар болох вэ?

    Хариу харах

    [1, 4, 5]. Pivot 4 нь index 1 дээр буулаа.

  2. Quickselect дунджаар хэдэн алхам хийх вэ?

    Хариу харах

    2n орчим. Хэсэг бүр өмнөхөөсөө ойролцоогоор хоёр дахин богино.

  3. Яагаад эрэмбэлэгдсэн array дээр удаан вэ?

    Хариу харах

    Pivot үргэлж хамгийн том нь болж, хэсэг ердөө нэгээр л багасна.

Гурван дадлага

Hint-ээ нээхээс өмнө өөрөө оролдоорой.

  1. 1.a = [6, 3, 8, 2, 5], k = 2 дээр хуваалт бүрийн дараах array-г бич.

    Hint харах

    Эхлээд k-г 1 болгоно, учир нь байр 0-ээс эхэлнэ.

    Хариу ба тайлбар

    Pivot 5: [3, 2, 5, 6, 8], i = 2 > 1 тул r = 1. Pivot 2: [2, 3, 5, 6, 8], i = 0 < 1 тул l = 1. l = r тул зогсоно. Хариу 3.

  2. 2.Pivot-ыг санамсаргүй сонгодог болго.

    Hint харах

    Хуваалтын өмнө санамсаргүй элементийг a[r]-тай соль.

    Хариу ба тайлбар

    swap(a[l + rand() % (r - l + 1)], a[r]); мөрийг pivot сонгохын өмнө нэмнэ. Үлдсэн код хэвээр.

  3. 3.n тооноос хамгийн бага k тоог (дараалал хамаагүй) дунджаар O(n) хугацаанд хэвлэ.

    Hint харах

    k дахь хамгийн багыг олсны дараа array ямар байдалд байна вэ?

    Хариу ба тайлбар

    Quickselect дууссаны дараа эхний k байранд хамгийн бага k тоо байрлана. Тэднийг шууд хэвлэнэ. C++-д nth_element(a, a + k - 1, a + n) ижил үр дүн өгнө.

Жишээ

Оролт

7 4
7 2 9 4 1 8 3

Гаралт

4

Одоо өөрөө бодоод үз

Бодлого

Хичээл

Энэ сэдвийн хичээл удахгүй нэмэгдэнэ.