תסבוכת...

[ש ב ו ז]

תסבוכת...

חידה לפנים! נתונה סדרה בת N איברים (N נתון כקלט) המורכבת מ A מספרים החוזרים על עצמם K פעמים ועוד מספר אחד המופיע פעם אחת בלבד, המטרה למצוא אותו. לדוגמה עבור: 10 (זה N) 3 4 3 7 3 4 4 8 8 8 הפלט יהיה 7.

 

[Yoava333]

K נתון לנו?

 

[Yoava333]

טוב יש לי

לא פתרון יעיל מי יודע מה, אבל זה עובד, מערך מונים...

 

[GuestOfHonor]

אבל - איך נדע מה גודל המערך?

למרות שאפשר להגדיר אותו בגודל 2/(N-1) (אם מובטח לנו שחוץ מאיבר אחד, כל האחרים חוזרים על עצמם). אפשרות שניה היא להגדיר רשימת מונים. בטח יש דרך פי 1000 יותר יעילה שאני לא חושב עליה.

 

[ש ב ו ז]

לא את זה אני מחפש...

מערך מונים הוא לא פיתרון... K לא נתון אבל ניתן למצוא אותו ב O)N( אז נגיד שהוא נתון...

 

[LevPolevoy]

האם הערכים נתונים בתוך מערך או ש

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

 

[ש ב ו ז]

זאת דווקא כן בעיה.

אני לא מחפש אלגוריתם נאיבי, אני מחפש אלגוריתם יעיל. אם זה משנה לך תקלוט אותם איך שבא לך אחד אחד או במערך.

 

[suff]

כמה יעיל?

 

[ש ב ו ז]

כמה שיותר...

ובכל אופן יותר יעיל מ o(n^2) שזאת הסיבוכיות הנגזרת מהפתרון הנאיבי

 

[suff]

nlogn

עץ מאוזן עם מונים על הקודקודים. מופעים כפולים מתלכדים ונספרים במונה. סרוק ומצא את היחיד. לדעתי יש פתרון ב (o(n שמתבסס על מיון מהיר. זה מספיק טוב?

 

[ש ב ו ז]

לא לזה

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

 

[גיל14]

מערך מונים

הוא בO zz.

 

[suff]

A כפרמטר? כקבוע?

כי מיון מניה הוא תלוי טווח ולא גודל. הרס הקלט? הממ... לגבי מיון מהיר זה לא מה שהתכוונתי אבל כרגע לא עולה לי הטריק שם, אז לא משנה. אם היית יודע כמה מהיר אפשר - היה עוזר.

 

[ש ב ו ז]

A לא כפרמטר מכיוון שהוא תליו בK

אני לא יודע מה הסיבוכיות המינימלית... השאלה לקוחה מאולימפיאדת מדעי המחשב של מדינות הבלקן

 

[suff]

שתהיה בריא

 

[אמיתי ר]

תיקון של הרעיון שלו

עת אדום שחור. מספר הצמתים יהיה סדר גודל של N/K ולכן זמן הבניה של העץ (כל צומת יהיה בעל מפתח שונה ומונה) NLG(N/K) שזה סדר גודל של NLGN וכמובן אח"כ סורקים את העץ למצוא לאיזה מונה יש ערך 1 סה"כ הזמן NLGN אופציה אחרת, שמתבצעת באותה סיבוכיות: למיין את הקלט (נניח בעזרת מיון-מהיר-אקראי, כך שזמן הריצה NLGN) כעת, נעבור מהאיבר הראשון עד האחרון בלולאה. אם האיבר במקום הנוכחי, שווה לאיבר הקודם, נגדיל מונה כלשהו. אם המונה התאפס אחרי K הופעות, סבבה, ממשיכים אבל אם המונה התאפס לאחר שהמונה היה רק 1 (כלומר הופעה בודדת של המספר) אז מצאנו את המספר שמופיע פעם אחת. ככלל , השאלה אינה מסובכת, ויש דרכים אבות לפתור אותה (כולם אבל עם סדר גודל של NLGN)

 

[suff]

עץ אדום שחור = עץ מאוזן

וגם יש AVL ועוד הצעות. לדעתי יש דרך לפתור את זה ללא מיון השוואות, ולכן בצורה קצרה יותר. אבל אני עסוק בסימולציה של A-STAR, ולכן לא היום...

 

[inbal76]

פתרון?

1. אם K לא נתון אז מוצאים אותו במעבר אחד על המערך. 2. עושים סיכום של ה-1-ים ביט-ביט על כל המספרים. ביט שסכום ה-1-ים בו מתחלק ב-K - הוא 1 ביט שלא - הוא 0 התוצאה תיתן את המספר המבוקש. הסיבוכיות תהיה O של N (כפול גודל היצוג הנתון במערכת, שלא תלוי ב-N) הערה: אם K זוגי אז במקום סעיף 2 אפשר לעשות XOR על כל המספרים ולקבל את התוצאה (שזה בערך אותו דבר בתכל'ס). מקווה שאני לא טועה כי כבר מאוחר וקשה לי לבדוק את עצמי, אז אנא תבדקו.

 

[inbal76]

תיקון קטן: בסעיף 2 זה להיפך כמובן

אם סכום ה-1-ים מתחלק ב-K זה 0 לא מתחלק -> 1

 

[ש ב ו ז]

קבלי ../images/Emo127.gif עצבני!