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

נתונות המחלקות הבאות:

public class IntNode {
private int _value;
private IntNode _next;
public IntNode(int val, IntNode n) {
_value = val;
_next = n;
}
public int getValue() {
return _value;
}
public IntNode getNext() {
return _next;
}
public void setValue(int v) {
_value = v;
}
public void setNext(IntNode node) {
_next = node;
}
}

נתונה רשימה מקושרת באורך n של מספרים שלמים הממומשת בעזרת המחלקה IntList שלהלן:

public class IntList {
private IntNode _head;
public IntList( ) {
_head = null;
}
public IntList (IntNode node) {
_head = node;
}
. . . // methods
}

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

עליכם להוסיף שיטה בשם isSubset למחלקה IntList, חתימת השיטה היא:

public boolean isSubset (IntList other)

השיטה מחזירה true אם הקבוצה other היא תת-קבוצה של הרשימה עליה מופעלת השיטה.

לדוגמא:

אם A מייצגת את הקבוצה 1, 4, 2, 8 ו-B מייצגת את הקבוצה 4, 8

אז הקריאה A.isSubset(B) תחזיר true והקריאה B.isSubset(A) תחזיר false

השיטה שתכתבו צריכה להיות יעילה ככל הניתן

מה שחשבתי לעשות זה למיין את 2 הרשימות בעזרת merge sort שזה עולה 2 * nlogn ובסה"כ nlogn ואחרי זה בעזרת הפונקציה שלי לבדוק:

        public bool isSubset(IntList other)
        {
            bool result = false;
            IntNode listNode = _head;
            IntNode otherListNode = other._head;


            while (listNode != null)
            {
                if (listNode.getValue() != otherListNode.getValue())
                    listNode = listNode.getNext();


                else
                {
                    if (otherListNode.getNext() == null)
                        return true;
                    listNode = listNode.getNext();
                    otherListNode = otherListNode.getNext();
                }

            }


            return result;
        }

אז זה יוצא סיבוכיות של nlogn + n ובסה"כ nlogn.

נערך 2014 בינואר 1511 שנים על-ידי falukky

מישהו ??

אתה בטוח שהסדר של האיברים לא חשוב?

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

תבדוק גם את מותר לך לשנות את הרשימה שלך (אחרת תצטרך להעתיק אותה)

העתקתי את השאלה כמו שהיא.

אפשר בבקשה הסבר על הפיתרן הליניארי ?

מכיר hashtable?

לא למדנו את זה בקורס

אז הפיתרון ב-(O(N לא רלוונטי.