שלום,
השימוש ב-QuickSort או בכל אלגוריתם אחר שלמדנו בשאלה זו איננו תקין - שימו לב שאנחנו נמצאים במרחב שניתן לבצע רק = וב-QuickSort ובכל אלגוריתם אחר שלמדנו יכולנו לבצע גם את שאר פעולות השיוויון >,<.
חשבתי על פתרון, אבל אני לא יודע איך להוכיח את נכונותו - אולי אתם תצליחו, אם כן ספרו לי.
נשווה בין כל זוג איברים צמודים במערך ו"נצמיד" להם את הערך true. אם במערך מספר אי זוגי של איברים ניתן לערך האחרון את הערך true (אין עם מי להשוות אותו) - ביצענו עתה n/2 השוואות. אם קיבלנו רק זוג אחד שהחזיר true זה המועמד היחד שלנו להיות המספר המיוחד ואז נסרוק את המערך ונבדוק האם הוא מופיע כמספר הפעמים שנדרש בשאלה. אם לא נחזיר שאין איבר שכזה. אם קיבלנו יותר מזוג אחד שהחזיר true "נעתיק" את המערך למערך עזר בלי הכפילויות של הערכים שהחזירו true ונבצע את אותה הבדיקה. נמשיך עם ההעתקת האיברים והבדיקה באופן רקורסיבי כאשר תנאי העצירה שלנו הם או שיש זוג אחד שמחזיר true (זכרו שיש גם את הערך הבודד האחרון שמחזיר true) או שנקבל על כל ההשוואות false.
! - הרעיון הוא שמאחר והאיבר הזה מופיע ממש יותר מ-n/2 פעם (גדול ממש!) הוא בהכרח יהיו קיימים במערך זוג מופעים צמודים שלו.
לדוגמא המערך [1,1,2,2,2,3,1,1,1] -> [1,2,2,3,1,1] -> רק זוג האחדים בסוף מחזיר true ולכן הוא המועמד היחיד.
שימו לב שהכוונה בהשוואת זוגות היא (למשל לפי הדוגמא) השוואת 1,1 ואז 2,2 ואז 2,3 ואז 1,1 ואז 1 (איבר בודד).
בנוגע לסעיף לאחריו. בגלל שנתון שיש איבר שכזה חסם תחתון על ההסתברות שבחירה אקראית של איבר במערך תהייה האיבר הזה היא $1/(n/2+1($ ולכן העיקרון כאן הוא שהסיכוי שיהיה cluster של האיבר הזה בסוף המערך הוא ממש נמוך -> נבחר את n/2 האיברים הראשונים ולכל אחד מהם נבצע n/2 השוואות (החל מהנקודה שהם מופיעים - כאשר אנחנו מתחילים מהאיבר הראשון ולאחר מכן השני …) נבצע את הבדיקה הזאת רק לn/2 האיברים הראשונים במערך, אחד מהם חייב להיות האיבר שלנו (כי נתון שקיים כזה) ולכן חישוב התוחלת הסיכוי שבחרנו את האיבר המיוחד כפול n/2 האיברים הראשונים כפול n/2 ההשוואות שאחנו מבצעים וזה יוצא O(n)
(לא כתבתי מספרים כי זה יוצא ג'יבריש - מקווה שהניסוח בעיברית מספיק)
אלה הפתרונות המוצעים שלי - אם אתם מצליחים להוכיח את הסעיף הראשון ספרו לי - ואם את חושבים שיש בעיה - ספרו לי - כי אני חושב שזה נכון וזה לא סבבה לשמור לעצמכם ידע.
ועוד משהו, שימו לב שע"מ "להפעיל" את הסידרה הגרועה ביותר עבור הסעיף הראשון נצטרך מערך בסגנון [1,1,1,1,2,2,2,2,1]