الگوریتم حذف عناصر تکراری از لیست به این صورت است که لیستی یک بعدی(1st) و یک عدد(N) به شما داده می‌شود. به شما گفته می‌شود که حداکثر تکرار مجاز در این لیست به اندازه‌ی عدد داده شده(N) است. از شما می‌خواهند که لیست جدیدی را بدون اینکه ترتیب عناصر به‌هم بریزد،با این شرایط از لیست اولیه ایجاد و چاپ کنید.

برای درک بهتر موضوع مثالی میزنم. فرض کنید که [1,2,3,1,2,1,2,3] به شما داده می‌شود و گفته می‌شود که حداکثر تکرار مجاز در این لیست N = 2است. الگوریتم شما باید از ابتدای لیست داده شده حرکت کند و عناصر [1,2,3,1,2] را به لیست جدید اضافه کند. اما نباید عناصر [1,2]که در اندیس ۶و۷ لیست اولیه هستند را وارد لیست جدید کند. زیرا حداکثر تعداد مجاز ۲ می‌باشد که عناصر ۱ و ۲ در لیست جدید به حداکثر تعداد مجاز رسیده‌اند. پس عناصر [1,2]را نادیده گرفته و به سراغ آخرین عنصر لیست اولیه یعنی عدد ۳ می‌رود و آن را اضافه می‌کند. الگوریتم شما در نهایت باید لیست [1,2,3,1,2,3]را نمایش دهد.

پیش از ادامه مطالعه از شما می‌خواهم کمی در رابطه با راه‌حل فکر کنید…

راه‌حل اول مرتبه اجرایی O(n2)

الگوریتم ما در لیست اولیه گردش ‌می‌کند و عناصر را از ابتدا به لیست جدید اضافه کند. هنگام اضافه کردن عنصری به لیست جدید، تعداد تکرار آن را در لیست جدید می‌شمارد. به کد زیر دقت کنید:

# Time complexity O(n^2)
def delete_nth_naive(array, n):
    ans = []
    for num in array:
        if ans.count(num) < n:
            ans.append(num)
    return ans

در خط ۳ ابتدا یک لیست جدید(ans) برای ذخیره نتیجه‌ی کار ایجاد می‌شود. در خط ۴ حلقه‌ای روی لیست اولیه(array) گردش می‌کند. در خط ۵ شرطی تعداد تکرارهای آن عنصر را در لیست نتیجه(ans) می‌شمارد. در صورتی که تعداد تکرار کمتر از حد مجاز باشد، آن عنصر به لیست نتیجه اضافه می‌شود(خط ۶). خط ۷ کد نیز نتیجه را باز می‌گرداند. همانطور که می‌بینید مرتبه‌ی اجرایی این کد O(n2) است. زیرا یک حلقه روی لیست اولیه گردش می‌کند و حلقه‌ی دیگری شمارش را در لیست نتیجه(مرتبه n) انجام می‌دهد.

راه‌حل دوم مرتبه اجرایی O(n)

راه دیگر برای الگوریتم حذف عناصر تکراری با مرتبه‌ی اجرایی پایین‌تر برای مسئله این است که هر بار، که عنصری به لیست جدید اضافه می‌شود تعداد آن نیز شمارش شود و در دیکشنری(کالکشن) ذخیره شود. کد زیر را ببینید:

# Time Complexity O(n), using hash tables.
import collections

def delete_nth(array, n):
    result = []
    counts = collections.defaultdict(int)  # keep track of occurrences

    for i in array:

        if counts[i] < n:
            result.append(i)
            counts[i] += 1

    return result

خط ۲ کتابخانه collections پایتون را ایمپورت می‌کند. خط ۵ لیستی برای ذخیره نتیجه ایجاد می‌کند. خط ۶ یک دیکشنری از نوع difaultdict ایجاد می‌کند.

تفاوت این نوع دیکشنری با دیکشنری معمولی در این است که هنگام نبودن کلیدی در دیکشنری خطا نمی‌دهد و آن را به دیکشنری اضافه می‌کند و مقدار آن را برابر مقدار پیش فرض تعیین شده در پرانتز روبروی آن می‌گذارد. در مثال ما چون در پرانتز روبروی آن int تعریف شده است بنابراین کلیدهایی که به دیکشنری اضافه می‌شوند دارای مقدار پیش‌فرض صفر هستند.

خط ۸ کد حلقه‌ای را روی لیست اولیه ایجاد می‌کند(مرتبه اجرای O(n)). خط ۱۰ به دیکشنری مراجعه می‌کند و مقدار کلید(عنصر) را با حداکثر تکرار مجاز مقایسه می‌کند(مرتبه اجرای ثابت O(1)). در صورتی که مقدار کلید از حداکثر تکرار مجاز کمتر باشد، عنصر به لیست نتیجه افزوده می‌شود(خط ۱۱). خط ۱۲ به مقدار کلید در دیکشنری یک واحد اضافه می‌کند تا در مقایسه‌های بعدی منظور شود. خط ۱۴ نتیجه را باز میگرداند.

همانطور که در توضیحات نشان داده شد، مرتبه‌ی اجرایی این راه‌حل O(n) است که نسبت به راه‌حل اولی مناسب‌تر است. هر دوی این کدها نیز در گیت‌هاب من قابل دسترسی است که می‌توانید استفاده کنید.

امیدوارم این پست webpy نیز مفید واقع شده باشد. پیشنهادات و انتقادات شما را به دیده‌ی منت می‌گذارم.

برچسب گذاری شده در: