Дундаж

Тавил:
N (N<=10000) урттай натурал тоон дараалал өгөгдөв. Аль нэг хоёр (тэр хоёрынхоо нэг нь өөрөө байж болно) элэмэнтийнх нь арифметик дундаж болдог дарааллын элэмэнтийг дундаж гэе. Тэгвэл уг дараалалд хичнээн дундаж байгааг тоол.
Эх өгүүлбэр

Бодолт:
Эхлээд уг дарааллаа эрэмбэлье. (Quicksort ~ O(N*LogN))
Дараа нь уг эрэмбэлэгдсэн дарааллын аль нэг элэмэнтийг (K дугаарх) дундаж мөн эсэхийг тогтооё.
Хэрвээ аль нэг хөрш элэмэнт нь тухайн элэмэнттэй тэнцүү бол тэр элэмэнт дундаж болж чадна.
(A[K+1] == A[K] OR A[K] == A[K-1])

Аль ч хөрш нь өөртэй нь тэнцүү биш бол өөрөөс нь их болон бага нэг нэг элэмэнтийн дундаж л байх боломжтой. A[K] = (A[K-j] + A[k+i]) / 2
Мөн A[K+i]-A[K] болон A[K]-A[K-j] ялгаварууд хоорондоо тэнцүү үед л уг A[K] элэмэнт маань дундаж болно гэж үзэж болох ба i, j өсөхөд тус ялгаварууд мөн дагаж өсөх тул хэрвээ аль нэг ялгавар нь нөгөөгөөсөө бага байвал тухайн i юм уу j коэффицэнтийн утгыг нэмээд яваад байх боломжтой.
if (A[K+i]-A[K] < A[K]-A[K-j]) i++; else j++;
Гэхмэтчилэнгээр дарааллын аль нэг зах хүртэл юм уу, K дахь элэмэнт дундаж болох нь батлагдах хүртэл энэ давталтыг явуулна.

Уг бодолт нь хамгийн муу тохиолдолд O(N*N) юм. Гэхдээ дундаж тохиолдолд үүнээс хамаагүй хурдан ажиллана.