שאלה במבוא למבני נתונים ואלגוריתמים

[uvdude]

שאלה במבוא למבני נתונים ואלגוריתמים

נתון מערך A בגודל n, עם איברים לא בהכרח שונים. צריך למצוא ערכים x,z שמקיימים: - x < z - לא קיים במערך שום ערך y שמקיים x < y < z - הערכים x ו-z מופיעים במערך ביחד יותר מn/2 פעמים בסעיף הראשון הוכחתי שהחציון של A בהכרח שווה לx או z. בסעיף השני צריך למצוא אלגוריתם שמוצא את x ו-z בזמן ריצה לינארי. חשבתי על משהו בכיוון של מיון מנייה (אבל לא נתון לי שום דבר על המספרים במערך) או מיון בסיס, אבל אני לא מצליח להתקדם משם. ברור שאני יכול לקבל את החציון בעזרת select (מציאת איבר במיקום n/2) ולקבל את אחד המספרים. אבל המערך לא ממויין ואני לא יכול להמשיך לעשות selectים עד כלות... יש הצעות?

 

[patch81]

אולי ערימה זה הכיוון

אני לא סגור על זה אבל... יש לך את אחד האיברים שהוא החציון. מה אם תבנה ערימת מכסימום מהחצי התחתון וערימת מינימום מהחצי העליון. זה יתבצע בזמן ליניארי. אם בנוסף תסכום כמה פעמים הופיע האיבר המכסימלי בערימת המכסימום והמינימלי בערימת המינימום. עכשיו אתה יודע כמה איברים הכנסת לשתי הערימות וכך יודע את מספר המופעים של החציון שלך. עכשיו מה שנשאר זה לחבר למספר המופעים של השורש של ערימת המינימום והשורש של ערימת המכסימום. הם בהכרח העוקב והקודם של החציון.

 

[MmMm20]

נסיון לפתרון...

תעשה באמת select ותמצא את האיבר x או z(נקרא לו k). כעת תעבור פעם אחת על המערך ותמצא את השני איברים הכי "קרובים" ל-k מלמעלה ומלמטה. ז"א תמצא שני איברים שאחד מהם מקיים k1<k ו-k<k2 כך שהם מקיימים שאין אף y שנמצא ביניהם. עכשיו תבדוק איזה מן הזוגות (k,k1) ו -(k,k2) מופיע יותר מ- n/2 פעמים ואלה ה-x ו-z שלך. מקווה שהייתי ברור, ושהפתרון נכון.

 

[uvdude]

אכן פשוט ועובד - תודה!