רוטר - אפשר כיוון כללי בפתרון שאלה מסוימת?

יומן פעילות	לוח שנה	מבזקי חדשות	תקנון	RSS	כותרות	כותרות לפי תגובה	ניקוי קוקיז	IP	להורדת אפליקציה
eBay	AliExpress	GearBest	Amazon	Booking	Kiwi	SkyScanner	Trip Advisor

"אפשר כיוון כללי בפתרון שאלה מסוימת?"

גירסת הדפסה

קבוצות דיון פיתוח, תיכנות ובניית אתרים נושא #14142	מנהל סגן המנהל מפקח Winner צל"ש מומחה

אשכול מספר 14142

TheBinary

דרג אמינות חבר זה

06:18 27.05.07

אפשר כיוון כללי בפתרון שאלה מסוימת?

אני צריך לכתוב שיטה שמקבלת מערך של מספרים שלמים, ובודקת אם יש בו מספר שחוזר על עצמו פעם אחת בלבד. (לא רקורסיבית)
אם יש בו מספר שחוזר על עצמו פעם אחת בלבד, היא מחזירה true. אחרת, false.
הבעיה היא - אני צריך לכתוב שיטה בסיבוכיות של לפחות O(n log n). חשבתי על דרך לפתור אותה רק ב-O(n^2) - הדרך הפשוטה הראשונה שעולה לראש.
אני לא רוצה פתרון, אלא רק כיוון כללי כי אני רוצה לפתור את השאלה לבד

תודה.

שתף

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

האשכול	מחבר	תאריך כתיבה	מספר
כנס	עידן_הכלי	27.05.07 21:11	1
לא נראה לי הגיוני,	TheBinary	27.05.07 23:19	2
לא מדוייק	עידן_הכלי	28.05.07 21:05	3
כן, יש לי גם עוד שאלה בנושא הזה של יעילות :\|	TheBinary	28.05.07 21:15	4
אממ	עידן_הכלי	28.05.07 21:55	5
הממ	Net_Boy	29.05.07 22:16	6
כן גם אני חשבתי על זה הרגע חחח	TheBinary	30.05.07 23:17	7
נראה לי שפתרתי	איש-האבוקות	31.05.07 12:08	8
תותח אתה :P	TheBinary	31.05.07 16:27	9
מזה num, ומאיפה בא עוד מערך?	FireAngel	04.06.07 23:37	11
חשבת על חיפוש בינארי ?	evi	03.06.07 22:56	10
חיפוש בינארי עובד רק על מערך ממוין.	TheBinary	05.06.07 18:08	12

עידן_הכלי

דרג אמינות חבר זה

21:11 27.05.07

1. כנס
בתגובה להודעה מספר 0

ערכתי לאחרונה בתאריך 27.05.07 בשעה 21:12 בברכה, עידן_הכלי

יש לי רעיון לפתרון, אני אנסה להסביר בכלליות:
קח HashTable , ועבור כל מספר שאתה בודק:
אם ל HT אין KEY בשם של המספר אז תוסיף KEY כזה,
אם ל HT יש KEY בשם של המספר, אז תמחק אותו מהHT.
בסוף הריצה אתה בודק אם קיים איזשהו KEY ב HT, אם כן אז יש לך מספר שמופיע רק פעם אחת.
זה הכי קרוב ל O(nLogn) שאפשר להגיע...

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

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

TheBinary

דרג אמינות חבר זה

23:19 27.05.07

2. לא נראה לי הגיוני,
בתגובה להודעה מספר 1

חשבתי על זה כבר, כדי לעבור על ה-Hash Table אתה צריך עוד לולאה מקוננת
וזה כבר נותן לך O(n^2)

משום מה נראה לי שצריך איכשהו לשלב חיפוש בינארי או וריאציה שלו

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

עידן_הכלי

דרג אמינות חבר זה

21:05 28.05.07

3. לא מדוייק
בתגובה להודעה מספר 2

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

אתה בטוח שהבנת את השאלה נכון?

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

TheBinary

דרג אמינות חבר זה

21:15 28.05.07

4. כן, יש לי גם עוד שאלה בנושא הזה של יעילות :|
בתגובה להודעה מספר 3

ערכתי לאחרונה בתאריך 28.05.07 בשעה 21:17 בברכה, TheBinary

public boolean what(int{} arr1, int{} arr2, int num)
{
  for (int i=0; i<arr1.length; i++)
    for (int j=0; j<arr2.length; j++)
      if (arr1{i}+arr2{j}==num) return true;
  return false;
}
נתון שהמערכים ממוינים בסדר עולה ממש (ממש זאת אומרת ללא מספרים זהים)
צריך לפתור את השאלה בסיבוכיות של O(n) (פתרתי כבר בסיבוכיות של O(n log n) וזה לא מספיק טוב)

תחליף את הסוגריים המסולסלים בסוגריים מרובעים :|

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

עידן_הכלי

דרג אמינות חבר זה

21:55 28.05.07

5. אממ
בתגובה להודעה מספר 4

לא בדיוק הבנתי את השאלה,

אבל בכל מקרה, הייתי מוסיף לשם עוד תנאי כי אם אתה יודע שהמערך ממויין תוסיף תנאי שהאיבר שאתה בודק אותו עכשיו לא גדול מnum, אם כן, אין לך מה לבדוק את שאר המערך.

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Net_Boy

חבר מתאריך 1.4.02
17151 הודעות, 1 פידבק, 2 נקודות

22:16 29.05.07

6. הממ
בתגובה להודעה מספר 0

אפשר למיין עם quicksort (n log n)
http://en.wikipedia.org/wiki/Quicksort
אחרי המיון לעבור על המערך עד שאתה מגיע לאיבר שאתה רוצה , לבדוק את האיבר ה n+1 אם הוא שווה לאיבר שאתה רוצה אתה מחזיר false אחרת true
הסדר גודל , הוא n + n log n שזה בסופו של דבר טטה של n log n

זהו

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

TheBinary

דרג אמינות חבר זה

23:17 30.05.07

7. כן גם אני חשבתי על זה הרגע חחח
בתגובה להודעה מספר 6

ערכתי לאחרונה בתאריך 30.05.07 בשעה 23:37 בברכה, TheBinary

השאלה היא אם מתייחסים ל-quicksort בתור סיבוכיות של O(n log n)
אני חושב שכן, כי אני לא רואה פתרון יותר הגיוני כרגע.
והבדיקה בסוף היא:
int prev=a{0};
for (int i=1; i<a.length; i++)
{
if (a==prev) return false;
prev=a{i};
}
return true;
נכון?

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

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

איש-האבוקות

דרג אמינות חבר זה

12:08 31.05.07

8. נראה לי שפתרתי
בתגובה להודעה מספר 7

לא בדקתי את זה בצורה מושלמת אבל זה כנראה עובד

פסאודו קוד (תיישר לשמאל):
1. length(arr2)-1 -> j
2. 0 -> i
3. כל עוד i<length(arr1) וגם j>=0 אזי
3.1 אם (arr1(i) + arr2(j))<num אזי
3.1.1 i=i+1
3.2 אחרת אם (arr1(i) + arr2(j))>num
3.2.1 j=j-1
3.3 אחרת החזר אמת
4. החזר שקר

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

TheBinary

דרג אמינות חבר זה

16:27 31.05.07

9. תותח אתה :P
בתגובה להודעה מספר 8

מקרה גרוע f(n)=2n
סיבוכיות O(n)

תודה כזה פתרון פשוט חחח
חשבתי על להתחיל עם המערך הראשון מהסוף והשני מההתחלה אבל ירדתי מזה חח

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

FireAngel

דרג אמינות חבר זה

23:37 04.06.07

11. מזה num, ומאיפה בא עוד מערך?
בתגובה להודעה מספר 8

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

evi
חבר מתאריך 31.3.02
635 הודעות, דרג אמינות חבר זה

22:56 03.06.07

10. חשבת על חיפוש בינארי ?
בתגובה להודעה מספר 0

הסיבוכיות שלו היא : log n ואתה עושה אותו n פעמים..

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

TheBinary

דרג אמינות חבר זה

18:08 05.06.07

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

פתרתי כבר את השאלה,
אני ממיין אותו ע"י quicksort שזה O(n log n)
ואז בודק אם יש מספר שחוזר על עצמו פעם אחת - האלגוריתם הזה בכלל לא מסובך.

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד