אני לומד מבוא למדעי המחשב ואני צריך עזרה בפתרון התרגיל הבא: התרגיל הוא מפרק מצביעים ואנחנו עובדים בשפת C\C++

שאלה 6

. כתבו תוכנית הקולטת סדרה של מספרים שלמים חיוביים מן הקלט, הסדרה מסתיימת במספר -1

על התוכנית להדפיס את ערכי כל המספרים שמופיעים בסדרה 3 פעמים או יותר, ואת האינדקסים שלהם.

לדוגמא, עבור הקלט:

23422524342-1

התוכנית תדפיס כפלט:

2: 0,3,4,6,10

4: 2,7,9

הנחיות:

1. על התוכנית לרוץ ביעילות .nlog(n)

2. חלקו את התוכנית לפונקציות עזר, והקפידו על כללי תכנות נכון.

צריך עזרה בבקשה בדרך פתרון

אתה יכול להשתמש ב-

map<int, vector<int> >

המפתחות שלך אלו הם איברי הסדרה והערכים זה מספר הפעמים שבו הם מופיעים.

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

לאחר המעבר אתה פשוט מדפיס כל מפתח (האיבר בסדרה) ביחד עם איברי הווקטור שמשוייך לו (האינדקסים השונים בו הוא מופיע).

מכיוון שהכל במעבר אחד זה אפילו

O(n)

התרגיל הוא על שימוש במערכים, ואתה נותן לו לעבוד עם map?

בכל מקרה, תמיד כשאומרים לך nlogn דבר ראשון שאתה צריך לחשוב עליו הוא מיון.

אם מדובר בספרות ולא מספרים (כלומר 0-9) אתה יכול להגדיל כל מקום במערך (בגודל 10) ב-1 כל פעם שהוא נקלט.

^ כן זה הפתרון הכי נקי פה, זמן לינארי וזיכרון קבוע.

מכיוון שהכל במעבר אחד זה אפילו

O(n)

לא תמיד האמת, ברוב המקרים map ממומש כ red black tree, שזה עץ בינארי (שיודע לאזן את עצמו).

לכן בפועל אתה תקבל n log n ...

ולמה אנשים קוראים לסיבוכיות יעילות? אני רואה את זה פה בפורומים

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

יעילות = Efficiency. סה"כ יש קשר בין שני המונחים.

אכן map של STL ממומש ע"י עץ. בשביל מימוש יעיל יותר צריך hash map (שאינו חלק מהספרייה הסטנדרטית של ++C).