עבור לתוכן

שאלה ממבחן בג'אווה (איך אתם הייתם פותרים)

Featured Replies

פורסם

צריך ליצור שיטה שבודקת כמה מופעים יש למספר כלשהו במערך למשל {1,1,1,3,3,3,4,5,5,5,7,7,7,7,} וצריך לדעת כמה פעמים מופיע המספר 5

צריך לעשות את זה ביעילות מירבית!

אני עשיתי חיפוש בינארי ואז בדקתי כמה פעמים הוא מופיע מעל וכמה מתחת הבעיה שבמקרה הגרוע שכל המספרים במערך שווים זה יוצא On אז כנראה יורידו לי נקודות....(במקרה הטוב O1 במקרה הממוצע Ologn

איך אתם הייתם פותרים?

פורסם

מה נתון בדיוק לגבי המערך, מה צריך לעשות בדיוק, ומה בדיוק האלגוריתם שלך?

פורסם

אם המערך לא ממוין וכולו 5 אין מנוס אלא לבצע חיפוש ב-(O(n

אם הוא ממוין אז תעשה חיפוש למופע הראשון והאחרון.

פורסם
  • מחבר

המערך ממויין

לפי מה שהבנתי מסטודנט אחר שאפשר לפתור את זה בOlogn גם אם כל המערך שווה למספר אחד

מוצאים בעזרת 2 חיפושים בינארים את ההתחלה של המופע הראשון של המספר ואת המופע האחרון ואז מחסירים בינהם ומקבלים את התוצאה.

זה אפשרי לדעתכם?

פורסם
  • מחבר

נכון...

חבל שלא חשבתי על זה בעצמי.

ארכיון

דיון זה הועבר לארכיון ולא ניתן להוסיף בו תגובות חדשות.

דיונים חדשים