כאשר יש לי לדוגמא מערך {1,2,2,4,4,1,3,1} ואני רוצה את הדרך הכי יעילה בכדי למצוא אם יש מספר שמופיע רק פעם אחת

שבדוגמא זה המספר 3

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

אפשרי לעשות את זה בפחות מ logn?

אני מניח שאתה מתכוון nlogn, ולא lרק logn.

אפשר לעשות את זה ב-(o(n, במעבר אחר על המערך, ע"י שימוש ב-HashMap שפשוט סופר כמה פעמים מופיע כל מספר.

אני לא אמור להשתמש בHashMap

אז הכי יעיל זה nlogn בלי ה HashMap ?

כנראה.

תודה.

אפשר גם בלי hashmap ב-O(n) תחת הגבלות מסויימות:

אם יש לך מספרים אי שליליים שלמים ואתה יודע מה המספר המקסימלי שאתה יכול לקבל (אם אתה רק לא יודע מה המקסימלי, אז אפשר לעבור פעם אחת על המערך ולמצוא את המקסימום) אז-

צור מערך באורך n, כאשר n הוא טווח המספרים האפשרי שלך (למשל בדוגמה שלך - 0 עד 4), ואתחל אותו לאפסים.

רוץ על איברי הרשימה, כאשר עבור כל איבר עם ערך k, תעלה את התא k במערך שלך ב-1.

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

מצטער על ההסבר הכושל, אני עייף.

הפתרון שהצעת נקרא מיון תאים (bucket sort) ואם לדייק היעילות שלו היא גודל המערך שנוצר או גודל הקלט (n) , הגדול מבינהם.

בנוסף יש פה ניצול זכרון מאוד גבוהה.

לדוגמא עבור הקלט {1000000} - מערך עם איבר אחד, שיטת המיון תיצור מערך עם מיליון תאים בזכרון, תבצע מיליון פעולות איפוס, פעולת קידום אחת ובסוף צריך לעבור על המערך כדי לחפש ערכים ולכן עוד מיליון פעולות השוואה.

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

כלל אצבע - במיון זה משתמשים כאשר המרחק בין המינימום למקסימום ידוע מראש, הוא קטן מ nlogn על הקלט ויש מספיק זכרון! אחרת לא חסכנו כלום

לדוגמא, אם היה ניתן לנו מערך בגודל מיליון של מספרים בין 0 ל 10 לשיטת המיון הזאת היה יתרון משמעותי.

אתה מתכוון ל counting sort

וכל comparison sort הוא אומגה של n log n. די קל להוכיח, אבל ככה אני חושב על זה:

במקרה הכי טוב יש לך מבנה נתונים עם insert ב O של 1, והכל כבר ממויין. אתה מחזיק

בערך x, מה הדרך הכי יעליה למצוא (בעזרת השוואות, כמובן) את ה index שלתוכו x נכנס,

חיפוש בינארי, נכון? שזה log n, ואתה צריך לעשות את זה עבור כל x, כלומר n פעמים. לכן אתה מקבל n log n

אפשר האמת להשתמש ב counting sort עם גודל קבוע (m), ביחד עם quick sort ואז

אתה מקבל סיבוכיות זמן של (n log (n/m וסיבוכיות זיכרון m. והנה לך bucket sort

וכל comparison sort הוא אומגה של n log n. די קל להוכיח, אבל ככה אני חושב על זה:

במקרה הכי טוב יש לך מבנה נתונים עם insert ב O של 1, והכל כבר ממויין. אתה מחזיק

בערך x, מה הדרך הכי יעליה למצוא (בעזרת השוואות, כמובן) את ה index שלתוכו x נכנס,

חיפוש בינארי, נכון? שזה log n, ואתה צריך לעשות את זה עבור כל x, כלומר n פעמים. לכן אתה מקבל n log n

אמ, זו לא ממש ההוכחה, פשוט הראית כאן ש-insertion sort רץ ב-nlogn. אבל לא הוכחת פה שאין שום מיון אחר שעושה את זה יותר מהר.

קיימת הוכחה מתמטית שבמיון המתבסס על השוואות בלבד, חייבים לבצע אומגה של nlogn השוואות (ב-worst case כמובן). ההוכחה מופיעה בויקיפדיה.

כאשר יש לי לדוגמא מערך {1,2,2,4,4,1,3,1} ואני רוצה את הדרך הכי יעילה בכדי למצוא אם יש מספר שמופיע רק פעם אחת

שבדוגמא זה המספר 3

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

אפשרי לעשות את זה בפחות מ logn?

אני דיי גרוע ביעילות... תה יכול להסביר לי למה במקרה הזה זה nlogn?

,תודה מראש

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

וב"אין שום מגבלות" הכוונה היא שאין לנו שום הנחות על הקלט (כלומר על האורך שלו, טווח הערכים שלו וההתפלגות).

public boolean single(int[] values){
quickSort(values,0,values.length-1);
for(int i=0;i+1<values.length;i++){
if(values[i]!= values[i+1] )
{
if(i+2>=values.length||i==0)
return true;
if(values[i+1]!=values[i+2])
return true;
}
}
return false
}
[code][/left]

[left] [/left]

מצטער על הפיקשושים בקוד......

יוצא nlogn נכון?

אתה יכול לערוך את ההודעה הקודמת ולתקן אותה.

בכל מקרה, למה הסתבכת עם i+2?