ধরুন, আমাদেরকে এমন একটি সারি ডিজাইন করতে বলা হয়েছে যা অতি সম্প্রতি ব্যবহৃত উপাদানটিকে এর শেষে নিয়ে যায়। সারিটি পূর্ণসংখ্যা 1 থেকে n দিয়ে শুরু করা হবে। এখন আমাদের একটি ফাংশন তৈরি করতে হবে যাতে যখনই এটিকে কল করা হয়, এটি তার ইনপুট হিসাবে প্রদত্ত অবস্থান থেকে মানটিকে সারির শেষে নিয়ে যায়। আমরা ফাংশনটিকে একাধিকবার কল করব, এবং ফাংশনটি তার চলমান কাজ সম্পাদন করার সময় সারির শেষে বর্তমানে মানটি ফিরিয়ে দেবে৷
সুতরাং, যদি সারিটি n =5 মান দিয়ে শুরু করা হয়, বা এতে 1 থেকে 5 পর্যন্ত মান থাকে; এবং অবস্থান যেখানে সঞ্চালিত হয় যথাক্রমে 5, 2, 3, এবং 1, তাহলে আউটপুট হবে 5, 2, 4, 1
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- i :=অ্যারে সূচক - 1-এর অবস্থান, যেখানে সাজানো ক্রম বজায় রাখার জন্য ডানদিকে k মান সন্নিবেশ করা যেতে পারে
- x :=মুছে ফেলুন (k - index[i])th উপাদান থেকে ডেটা[i]
- র জন্য i+1 থেকে সূচকের আকারের পরিসরে, করুন
- index[ii] :=index[ii] - 1
- যদি ডেটার শেষ উপাদানটির আকার>=nn হয়, তাহলে
- তালিকা ডেটার শেষে একটি নতুন তালিকা ঢোকান
- তালিকা সূচকের শেষে n সন্নিবেশ করান
- ডেটার শেষে x ঢোকান
- যদি ডেটা[i] rmpty হয়, তাহলে
- ডেটা থেকে ith উপাদান মুছুন
- সূচী থেকে ith উপাদান মুছুন
- এক্স রিটার্ন
উদাহরণ
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
from bisect import bisect_right from math import sqrt class TestQueue: def __init__(self, n): self.n = n self.nn = int(sqrt(n)) self.data = [] self.index = [] for i in range(1, n+1): ii = (i-1)//self.nn if ii == len(self.data): self.data.append([]) self.index.append(i) self.data[-1].append(i) def solve(self, k): i = bisect_right(self.index, k)-1 x = self.data[i].pop(k - self.index[i]) for ii in range(i+1, len(self.index)): self.index[ii] -= 1 if len(self.data[-1]) >= self.nn: self.data.append([]) self.index.append(self.n) self.data[-1].append(x) if not self.data[i]: self.data.pop(i) self.index.pop(i) return x queue = TestQueue(5) print(queue.solve(5)) print(queue.solve(2)) print(queue.solve(3)) print(queue.solve(1))
ইনপুট
queue = TestQueue(5) print(queue.solve(5)) print(queue.solve(2)) print(queue.solve(3)) print(queue.solve(1))
আউটপুট
5 2 4 1
