ערכתי לאחרונה בתאריך 10.03.09 בשעה 18:05 בברכה, Deuce
לפני כמה שבועות אחד המשתמשים ביקש לכתוב שגרה שמקבלת מערך בו מופיעים מספרים, חלקם יותר מפעם אחת, ולהחזיר מערך בו כל מספר מופיע פעם אחת בלבד.אפשרויות טריוויאליות:
1. לאפס מערך חדש, לרוץ על המערך הקיים, להכניס אליו איברים במידה והוא לא מופיע במערך - O(n^2) זמן ו-O(n) מקום.
2. אם כבר עולה לנו n^2 אז בוא נמיין אותו בסיבוכיות של n^2 בעזרת מיון פשוט כמו bubble sort, נרוץ עליו ונמחק איברים כפולים ע"י השמה למערך חדש. החזרנו ככה מערך ממויין בלי כפולים ב-n^2.
3. בוא נמיין ב-nlog n (בעזרת מיון מיזוג, בעזרת מיון מהיר, בעזרת מיון ערימה - יש עוד אפשרויות) ונבצע כמו 2. נו טוב, זה עדיין nlog n זמן.
אני ידוע כאחד שלא מחפש את האפשרות הטריוויאלית:
כבר אז רציתי לפתור את זה בסיבוכיות זמן ליניארית (תוך כדי שימוש ליניארי במקום בזכרון, לא רוצה לחרוג מכך). אני מניח שזה כן אפשרי, אבל אני רוצה לנסות לשתף גם אתכם כי זאת נראית לי בעייה מענייינת.
שימו לב מה למשל לא טוב:
לאתחל מערך בגודל האיבר המקסימלי במערך הקלט ולהכניס אליו איברים בצורה של A[Ar[2]] = 1 - זה בעצם יסמל שהאיבר Ar[2] נמצא בקבוצת הקלט. למה זה לא טוב? כי אם למשל max term = n^4 (למשל אם המערך 1,2,3,256). הקצאתי סיבוכיות מקום של n^4 - נכון שזה לזמן קצר, אבל זה לא כצורך !
כיוון שאני הצלחתי לגייס כבר אז:
לבנות האשינג אוניברסלי שאמור בהסתברות גבוהה למפות כל איבר לתא בנפרד. במידה ויש התנגשות אז נרוץ על האיברים במערך ואם הוא כבר מופיע אז נמחק אותו, אחרת נפעל באמצעות chaining. בהסתברות גבוהה זה עונה על הדרישות, אבל עדיין יש מקרים חמקמקים.
גירסת הדפסה
סגן המנהל
מפקח
Winner
צל"ש
מומחה
