(۱۷ بهمن ۱۳۹۱ ۰۵:۱۴ ب.ظ)armin_b00ter نوشته شده توسط:  من به نظرم اینجوریه که میایم تو o(n) آرایه رو از مکان n/3 پارتیشن میکنیم و از n/3 تا آخر رو هم روی ۲n/3 پارتیشن می کنیم. حالا ما آرایه رو به سه دسته ی مجزا تقسیم کردیم. از ۰ تا n/3 ، از n/3 تا ۲n/3 و از ۲n/3 تا آخر. من معتقدم مقدار مورد نظر ما یا عنصر n/3ام آرایه است یا ۲n/3. واسه اینکه بفهمیم کدومه کافیه تعداد اونهارو تو دسته های مجاورشون بشمریم و بینیم که بیشتر ار n/3 هست یا نه که مجموعه ی این کارا توی o)n) انجام میشه.
در مورد این که چرا مطمئنم می تونی هر آرایه ی دلخواهی که شرایط مسئله رو داره می خوای بنویسی و بعد مرتبش کنی و آیتم n/3 و ۲n/3 امش رو در نظر بگیری که میشه همون مقداری که از پارتیشن به دست میاد. بعد میبینی که حتما همون عدد جوابه.
دلیل قانع کننده ترش اینه که وقتی از یه عددی بیشتر از n/3 داریم و هر دسته هم n/3 تا ظرفیت داره حتما این عدد تو ۲ تا دسته حضور داره و این امکان نداره بعد از پارتیشن یک عدد هم در سمت چپ محور باشه هم سمت راست محور مگر اینکه مقدارش با محور برابر باشه.
خیلی فکر کردم تا این جوابو به دست بیارم. نمی تونم سر کنکور چجوری باید اینو می فهمیدن بیچاره ها

(۱۷ بهمن ۱۳۹۱ ۰۵:۳۳ ب.ظ)۸Operation نوشته شده توسط:  روشتو قبول دارم آرمین جان!ولی وقتی می دونیم گزینه ۱ درسته این مدلی تحلیل می کنیم!قبول داری؟!
یعنی بشخصه من اگه سر جلسه این سوالرو ببینم عمرا توی اون وقت با اطمینان بزنم گزینه یک رو!
بهرحال ممنون