جواب کتاب درسته .
چند شکل میشه این الگوریتم رو نوشت :
1_ اول مرتب سازی کنیم بعد عناصر پشت سر هم رو بشماریم که میشه n+nlong عملیات که همون اوردر nlogn هست .
2_ یک balance search tree مسازیم با اسم مثلا t
یک بار آرایه رو از اول تا آخر شروع به پیمایش می کنیم بعد تعداد رو داخل t هر بار که یک عنصر دیدیم اضافه می کنیم .
پیمایش اوردر n هست و پیدا کردن logn که میشه nlogn .
3_ اگر بجای balanced search tree از hashtable استفاده کنیم اوردر میانگین میشه n ولی worst case میشه n^2
4_ اگر داخل آرایه عدد ذخیره شده باشه و رنج اعداد کوچیک باشه میشه بجای balanced search tree از یک آرایه با سایز بزرگترین عنصر استفاده کرد و هر عنصر رو با ایندکس پیدا کرد که این طوری اوردر میشه n . ولی چون سوال حرفی از عدد بودن نزده این کارو نمیشه کرد .(direct address table )
5_ اگر هم از disjoint set استفاده کنیم اوردر باز هم همون nlogn میشه (البته در حالت میانگین )