מאוד פשוט:

ציטוט:

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

נבנה מערך עזר בגודל 100 [ ]B(מאופס בתור התחלה), נעבור על המערך המקורי(מ1 עד 100) (נניח שמו [ ]A), ובכל פעם מבצעים השמה [ B[ i ]=A[ i;
ברור שבניה כזו עולה O(n).
לאחר שבצענו את בניית העזר תשובה לשאלה האם מספר X קיים במערך עולה בדיוק פעולה אחת.
פשוט בודקים האם 0=?[ B[ X , אם כן, אזי המספר אינו קיים, אחרת המספר קיים..

*כמובן שאת מערך העזר אפשר לבנות עוד בשלב הבניה הרנדומלית.. (ואז חסכנו את עלות הבניה..)

הנה

קוד:

int[] arr = new int[100];
int[] b = new int [100]
for(int i=0; i<arr.length; i++){ 
        arr[i] = (int) (1 + Math.random()*100);
		b[arr[i]] = arr[i];
}

boolean find(int x){
	if (x<1 || x >100)
		return false;
	return (b[x]!=0;
}	

אם רוצים את הדרישה הזו("יודפס מספר התא בו הוא מופיע לראשונה"), לא שמתי לב בהתחלה, אז פשוט אפשר ע"י שדרוג פשוט לתמוך גם בשאלתה מטופשת זו)

הנה זה עומד בדרישות..

קוד:

int[] arr = new int[100];
int[] b = new int [100]
for(int i=0; i<arr.length; i++){ 
        arr[i] = (int) (1 + Math.random()*100);
		if (b[arr[i]]==0)
			b[arr[i]]=arr[i]+i;
}

find(int x){
	if (x<1 || x >100)
		System.out.println("No!");
	else
		System.out.println("yes"+b[x]-x);
}