נו...
כדי לפתור את א' אתה עושה מערך מונים כלומר מערך באורך n שבו תמנה כמה פעמים מופיע כל מספר במערך שקיבלת. אם כל מספר מופיע פעם אחת (או לחליפין יש מספר שלא מופיע בכלל או יותר מפעם אחת) אזי לא כל המספרים מופיעים. כלומר, אני עובר על המערך ובודק לי איזה מספר הופיע ואיזה לא, מעבר כזה הוא בסדר גודל של theta
ומעבר נוסף על המערך העזר שלך נותן לך עוד פעם theta
ועלכן כל הקוד יהיה ביעילות של theta
.
בסעיף ב' צריך קצת יותר לחשוב, אני אומר מאחר והמספרים הם מ0 עד n-1 בדיוק כמו האינדקסים במערך אתה יכול לעשות מעין קפיצות עם מונה.
הרעיון שלי (לא ניסיתי, רק קונספט): אתה מתחיל עם מונה 0 מהתא הראשון במערך. אם שונה מ 1- שמור את המספר שהיה בתא, החלף את הערך בתא ב 1- קדם מונה וקפוץ לתא במספר ששמרת.
אם המספר שווה ל 1- קדם את האינדקס מבלי לקדם את המונה, שים לב לא לחרוג מהמערך, כלומר תשתמש ב% כדי להבטיח שלא משנה לאן תגיע האינדקס שלך יהיה בגבולות המערך
משהו בסגנון:
int checkArr(int* arr, int n)
{
int distinctNumCount = 0;
int jumpCount = 0
int curIndex = 0;
int nextIndex = 0;
while (jumpCount < 2*n)
{
if (arr[curIndex] != -1)
{
nextIndex = arr[curIndex];
distinctNumCount++;
arr[curIndex] = -1;
curIndex = nextIndex;
}
else
{
curIndex = (curIndex + 1) % n;
}
jumpCount++;
}
return (count == n ? TRUE : FALSE);
}
קח בחשבון שכתבתי ב 1 בלילה בnotepad בלי לנסות לקמפל אפילו, כנראה שזה לא ירוץ מפעם ראשונה אבל debugger חברו הטוב של האדם.
אני עושה בפונקציה עד 2n קפיצות, אני חושב שאפשר פחות, אבל בפועל זה לא משנה את הסיבוכיות זמן ריצה של הפונקציה והיא תישאר על O
