שלום לכולם

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

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

לדוגמא:

{2,4,6,8,7,3,4,8,2}
יחזיר: 6.

הסיבוכיות של הפונקציה שהיתה כתובה היא o(n²)

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

עכשיו השאלה שלי האם ניתן לפתור את השאלה בסביוכיות o(n)?

האם יש למישהו רעיון?

תודה לעוזרים

יש פתרון ב-(o(n, אבל הוא דורש להשתמש במבנה נתונים של קבוצה (set).

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

קודם כל תודה על התגובה.

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

הבעיה שהם ביקשו לפתור את זה ביעליות היעילה ביותר(ואני מפחד שלא יתנו לי את מירב הנק' על השאלה)

מה זה בדיוק מבנה נתונים קבוצה set?

set זה מבנה נתונים שמאפשר להכניס לתוכו איברים, להוציא ממנו איברים, ולבדוק אם איבר כלשהו קיים בתוכו, בסיבוכיות תיאורטית של (o(1.

אם אתה מתעקש, חפש בגוגל קצת על HashSet ב-java ואיך משתמשים בזה.

אוקי, תודה רבה רבה לך

public static int getSet(int[] arr){

HashMap<Integer,Integer>m=new HashMap<Integer,Integer>();

for(int i=0;i<arr.length;i++){//O(n)

m.put(arr, arr);//O(1)

}

return m.size();

}

אני מניח שהפתרון שהם ביקשו היה ה Logn מהסיבה שהפתרון ב HASHMAP הוא לא דטרמיניסטי

(שים לב להנחה המופיעה ב JAVADOC:

This class offers constant time performance for the basic operations (add, remove, contains and size), assuming the hash function disperses the elements properly among the buckets)

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

moranel: למה HashMap כשאפשר HashSet?

חוץ מזה, להבא תעטוף (תעטפי?) את הקוד בטג קוד (כפתור # למעלה) במקום להצמיד לשמאל.