בעיה בתרגיל יעילות בשפת java

[best view]

אהלן, תרגיל יעילות ממבחן.

הצלחתי לפתור בסיבוכיות זמן (O(n. הבוחן הוריד לי 17 נקודות מתוך 25.

רשם שיש אפשרות לפתור ב(O(logn. הקוד שלי הועבר למחשב איכשהו ורץ תקין.

האם יש פיתרון בסיבוכיות זמן (O(logn?

יש על מה לערער?

[zahit]

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

ה - log מרמז על פתרון שנראה כמו חיפוש בינארי איכשהו, אני מניח שאתה מכיר את הקונספט. הנקודה פה היא שבגלל שנתון לך שבהכרח כל מספר מופיע פעמיים (ברצף) ורק מספר אחת מופיע פעם יחידה, אתה יודע שמספר האיברים הכולל הוא אי זוגי, כלומר 2k+1 עבור איזשהו k>=0. זה מאפשר לך לבצע צעד כזה - נביט באיבר האמצעי (יש k מימינו ומשמאלו) ונשווה אותו עם האיבר שמשמאלו ועם זה שמימינו. אם הוא שונה משניהם אז הוא האיבר המבוקש וסיימנו. אחרת, הוא שווה לאחד מהם. אם נסיר את הזוג הזה (האיבר המקורי והשכן שלו ששווה לו) נשאר עם האיברים שהיו משמאל לזוג הזה בקבוצה אחת, ואלו שמימין בקבוצה שניה, כשבאחת k איברים ובשניה k-1 איברים. אחת מהקבוצות האלו היא בעלת מספר אי זוגי של איברים, ושם צריך להמשיך לחפש את האיבר הבודד באופן רקורסיבי (כי התכונה של "כל המספרים באים בזוגות חוץ מאחד", מחייבת מספר אי זוגי של איברים). מקווה שזה מובן...