שאלה

[ירדן132]

שאלה

שלום רוצים שנממש פונקציה שמקבלת מערך מלא במספרים ומחזירה TRUE אם קיים במערך איבר שמופיע פעם אחת בלבד במערך וFALSE אחרת. חשבתי על 2 דרכים: 1.למיין את המערך בעזרת QUICKSORT ואז לעבור על המערך ולמצוא איבר שמופיע פעם אחת,אם יש כזה. 2. לבנות מערך נוסף שישמש כאינדקס לאיברים של המערך המקורי,אבל הוא יכול להגיע לגדלים עצומים ולתפוס הרבה זיכרון. למישהו יש רעיון למימוש יעיל יותר?

 

[vinney]

מערך האינדקס יכול להיות HASH

ולא מערך בטווח המלא. ככה במקרה הגרוע ביותר לא תעברי את סיבוכיות הQUICKSORT, אבל במקרה הממוצע זה יהיה לינארי.

 

[ron369]

מה רע במימוש של ה-quicksort?

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