سوال:الگوریتم جست و جو nonUnique

[FastCode]

سلام.
یه سوال سخت دارم.
تعداد فوق العاده زیادی شی دارم که مرتب شده اند.
مثل:1,1,1,3,4,4,4,4,4,4,4,6,6

حالا یه الگوریتم(مثل باینری سرچ) میخوام که مکان اولین و آخرین item که مقداراون مثلا" 4 هست رو بده.
هر چیزی که دوست دارید بدید ولی LinearSearch نباشه.
با پیشاپیش

[qwerty11]

منظورت از فوقالعاده زیادتا چندتاست !؟

راستش این سوال کاملاً به این بستگی داره که شما چندتا search بخوای روی آرایت انجام بدی. چون اگر قرار باشه فقط یه دونه جستجو انجام بدی پیچیدگیش n میشه! اما اگر بخوای چندین تا جستجو روی آرایه انجام بدی اولش یه پیچیدگی n داری و بعداً هر جستجو رو میتونی تو log n انجام بدی. پس من فرض میکنم که هدفتون اینه که تعدادی جستجو روی آرایه انجام بدین :

دو تا آرایه در نظر بگیر، مثلاً first و last. یه آرایه ی دیگه هم به نام copy در نظر بگیر و داده های آرایه ی اصلی رو توش کپی کن. حالا مقداری که توی first[i] I باید قرار بدی برابر با اولین مکان i امین عنصر غیر تکراری هستش و مقداری هم که توی last[i] I باید قرار بدی برابر با آخرین مکان i امین عنصر غیر تکراری هستش. آرایه ی copy رو هم باید جوری تغییر بدی که copy[i] I شامل i امین عنصر غیر تکراری باشه. حالا با باینری سرچ روی آرایه ی copy باید مکان عنصر جستجو شده رو توی آرایه ی copy به دست بیاری (فرض کن j به دست اومد). حالا first[j] I شامل اولین ایندکس و last[j] I هم شامل آخرین ایندکس توی آرایه ی اصلی خواهند بود.

int dif=0;

first[0]=0;

copy[0]=a[0];

for(int i=1;i<n;i++){

    if(a[i]!=a[i-1]){

        last[dif]=i-1;

        first[++dif]=i;

        copy[dif]=a[i];

    }

}

last[dif]=n-1;

dif+1 تعداد عناصر غیر تکراری توی آرایه هستش. پس باید باینری سرچ رو از اندیس 0 تا dif روی آرایه ی copy انجام بدی. کاملاً واضحه کدی رو هم که بالا گذاشتم فقط یه بار باید انجام بدی.

[FastCode]

1,000,000 شی و 200,000 جستوجو.
مشکل اینحاست که اجبارا" یکی از لیست ها بر اساس چیز دیگه سورت میشه.
و مشکل دیگه اینه که من نمیتونم براحتی دسترسی به هر دو لیست داشته باشم.
قضیه ی چایلد و پرنت:اگر به دوتاشون دسترسی داشتم که با (O(n+m حل می شد.

[qwerty11]

میشه متن دقیق سوالتون رو قرار بدین !؟ با 1000000 عنصر و 200000 تا جستجو الگوریتمی که من گفتم تو زمان خیلی خوبی انجام میشه ! مگه شما چندتا لیست دارین که یکیشون اجباراً باید یه جوری سورت بشه !؟

درباره ی قضیه ی child & parent هم یکم توضیح میدی چی هست !؟ اولین باره که اسمشو میشنوم !

[FastCode]

میشه متن دقیق سوالتون رو قرار بدین !؟

سوالی به کار نیست دوست عزیز.من هیچ موقع وقت دوستان رو برای Homework هدر نمیدم.(یه نگاه به تاریخ تولدم هم بکن==> من دانشجو نیستم.)
ببخشید وقتتون رو گرفتم.فکر میکنم که یه راه پیدا کردم که به دوتاشون دسترسی پیدا کنم.اگر حل شد نتیجه ((O(m+n) رو میزارم دوستان استفاده کنن.
ممنونم از اینکه وقت گذاشتید.

[qwerty11]

homework !?
چرا تو اینجا به هرکی بگی بالای چشت ابرو هستش ناراحت میشه !؟
من به هیچ وجه منظورم homework نبود! هر چند که اگه آدم برای homework هم کمک بخواد از نظر من مشکلی نیست! کمک کردن به دیگران رو هم به هیچ وجه وقت تلف کردن نمیدونم ! ...

[FastCode]

ببخشید اگر ناراحت شدید.قصد ناراحت کردن شما رو نداشتم.فقط موقعی که گفتید سوال این سوال به ذهنم اومد که شاید شما فکر کردید من دانشجو هستم.
در ضمن با قضیه چشم و ابرو و ... کاملا" موافقم.