ת'רד חידות

[3d7]

קיים מערך בגודל n שכל אחד מהאיברים שלו מכיל מספר מטיפוס long.

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

צריך למצוא את המספר שמופיע במערך מספר אי-זוגי של פעמים בסיבוכיות של (O(nlogn.

דוגמה 1: 5 5 3 4 4 4 6 4 6 --> המספר שמופיע מספר אי-זוגי של פעמים הוא 3.

דוגמה 2: 3 2 2 2 4 3 4 --> המספר שמופיע מספר אי-זוגי של פעמים הוא 2.

[mandarin]

תמיין את המערך ותעבור מספר מספר ותספור האם המספר מופיע מספר זוגי או אי-זוגי של פעמים ?

[3d7]

נכון!

תביאו עוד חידות. :

[mandarin]

יש לך מערך של מספרים בגודל N ומספר משתנה X. איך ניתן בצורה הכי יעילה להגיד האם סכום 2 מספרים במערך שווים ל X (אתה יכול לבחור לענות ביעילות זיכרון או יעילות זמן).

[שניצל]

טוב, אני לא אהרוס את החידה (אני מכיר את האלגוריתם לפתרון של דברים כאלה), אבל אני אחוד עוד אחת:

ממשו קלאס המייצג מערך של int (בגודל מוגדר מראש N) שבו ניתן לבצע שלוש פעולות: לשים ערך בתא מסוים, לקחת ערך מתא מסוים, ולשים ערך בכל התאים:

class MyArray
{
public:
 void set(int i, int value);
 int get(int i);
 void setAll(int value);
};

הקאץ' הוא ששלוש הפעולות צריכות לעבוד ב-(O(1.

[cold fire]

יש לך מערך של מספרים בגודל N ומספר משתנה X. איך ניתן בצורה הכי יעילה להגיד האם סכום 2 מספרים במערך שווים ל X (אתה יכול לבחור לענות ביעילות זיכרון או יעילות זמן).

int vec[8]={1,2,3,4,5,6,7,8};
bool checkSum(int index1,int index2,int x)
{
	return vec[index1]+vec[index2]==x;
}

[mandarin]

אתה צוחק או מה ? זה בכלל לא עושה את מה שאמרתי... (אם לא הבנת, הקלט הוא מערך ו X ולא 2 אינדקסים ו X).

את הבעיה של שניצל הייתי פותר עם 2 מערכים. (ושניצל האם יש לך 2 אלגוריתמים, אחד שיעיל בזיכרון ואחד שיעיל בזמן ?)

[cold fire]

אז כנראה שלא הבנתי את השאלה

bool checkSum(int vec[],int x)
{
	for(int i=0;i<N-1;i++)
	{
		if(vec[i]+vec[i+1]==x)
			return true;
	}
	return false;		
}

אני מקווה שעכשיו הבנתי את השאלה

[mandarin]

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

עבור מערך 2 6 9 3 8 5 והמספר 17 התשובה היא שיש 2 מספרים כאלו, 8 ו 9.

[cold fire]

bool checkSum(int vec[],int x)
{
   for(int i=0;i<N;i++) {
     for(int j=0;j<N;j++) {
        if(i!=j && vec[i]+vec[j]==x)
             return true;
     }
   }
   return false;
}

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

[mandarin]

זה אפילו פתרון בכלל לא יעיל (אם כי נכון). מה שכן אפשר לעשות פתרון יותר יעיל מבחינת זמן אבל שיקח אותה כמות זיכרון (כמובן שאפשר לעשות פיתרון הרבה יותר יעיל מבחינת זמן אבל שיקח יותר זיכרון).

[EAD]

יש לך מערך של מספרים בגודל N ומספר משתנה X. איך ניתן בצורה הכי יעילה להגיד האם סכום 2 מספרים במערך שווים ל X (אתה יכול לבחור לענות ביעילות זיכרון או יעילות זמן).

פתרון נחמד (לא יחיד), תמיין הערכים במערך.

שים שני מצביעים, אחד לסוף המערך ואחד לתחילתו.

ותעבור עליו.

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

אם לא אז יש מספר אפשרויות

אם קטן, נעלה את המצביע של הראש (שמצביע לקטנים) ב1

אם הסכום גדול, נוריד את המצביע של הראש ב1 (המצביע של הגדולים)

אם נגיע למצב ששני המצביעים מתהפכים או מגיעים לאותו אחד (אין יותר אפשרויות) נחזיר כי אין וטעות.

מבחינת יעילות - סה"כ מיון של מערך NLOGN

אבל

אפשר ליצור שהמיון יהיה פה יותר יעיל.

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

ולגבי האחרים נשתמש במיון "דלי" (אנחנו יודעים שזה מאפס ועד המספר שלנו כולל) ונקבל מיון בסדר גודל של N.

זה כבר נראה לי די טוב ;D

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

שאלה ממש נחמדה למי שלא מכיר, וממש לא קלה

[mandarin]

למה לא קלה ? נראה לי שפיתרון של שימוש במערך עזר מפשט את הפיתרון.

והפיתרון שלך נכון.

[EAD]

^^

יש לך עוד דרכים לפתור את הבעיה?

אשמח מאוד לשמוע.

חשבתי על דרכים נוספות, נניח בלי למיין בכלל.

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

או דברים מתורת הגרפים - יש פה כמו זיווג בעצם על פי משקל מסויים.

ולגבי מה שאמרת עם מערך עזר, לא כזה פשוט.

תנסה ותראה.

[mandarin]

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