ধরুন আমাদের কাছে একটি অ্যারে আছে যাকে বলা হয়, nums এবং যেটি অ-হ্রাস না হওয়া ক্রমে সাজানো হয়েছে, এবং একটি সংখ্যা লক্ষ্য। লক্ষ্য একটি সংখ্যাগরিষ্ঠ উপাদান কিনা আমাদের খুঁজে বের করতে হবে. একটি অ্যারেতে একটি সংখ্যাগরিষ্ঠ উপাদান হল একটি উপাদান যা N/2 বারের বেশি দৈর্ঘ্যের একটি অ্যারেতে প্রদর্শিত হয়। তাই যদি অ্যারেটি − [2,4,5,5,5,5,5,6,6] এর মত হয়। এবং লক্ষ্য 5, তারপর আউটপুট সত্য।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- দুটি সাহায্যকারী মডিউল থাকবে, নিম্ন() এবং উপরের()। এগুলো নিম্নরূপ।
- লোয়ার() অ্যারে অ্যারে এবং টার্গেট দুটি আর্গুমেন্ট নেয়, সেটি হল −
- নিম্ন :=0, উচ্চ :=arr এর দৈর্ঘ্য
- যখন কম <উচ্চ −
- মধ্য :=নিম্ন + (উচ্চ - নিম্ন)/2
- যদি arr[mid] =টার্গেট, তাহলে high =mid, অন্যথায় low =mid + 1
- উচ্চ রিটার্ন যখন arr[high] =লক্ষ্য, অন্যথায় -1
- উপরের() দুটি আর্গুমেন্ট অ্যারে অ্যারে এবং টার্গেট নেয়, অর্থাৎ −
- নিম্ন =0, উচ্চ =arr এর দৈর্ঘ্য
- যখন কম <উচ্চ −
- মধ্য =নিম্ন + (উচ্চ - নিম্ন)/2
- যদি arr[mid] =টার্গেট, তারপর low =mid, অন্যথায় high =mid - 1
- রিটার্ন কম হলে arr[low] =লক্ষ্য, অন্যথায় -1
- প্রধান ফাংশন হবে − এর মত
- u :=upper(arr, target)
- l :=low(arr, target)
- সত্য ফেরত দিন, যখন u – l + 1> (সংখ্যার দৈর্ঘ্য) / 2 যদি u -1 না হয়, অন্যথায় মিথ্যা
উদাহরণ(পাইথন)
আসুন আরও ভালোভাবে বোঝার জন্য নিচের বাস্তবায়ন দেখি −
class Solution(object): def upper(self,n,target): low = 0 high = len(n)-1 while low<high: mid = low + (high - low + 1)//2 if n[mid] == target: low = mid else: high = mid-1 return low if n[low] == target else -1 def lower(self,n,target): low = 0 high = len(n)-1 while low < high: mid = low + (high - low)//2 if n[mid]== target: high = mid else : low = mid +1 return high if n[high] == target else -1 def isMajorityElement(self, nums, target): u = self.upper(nums,target) l = self.lower(nums,target) return u-l+1 >len(nums)/2 if u != -1 else False ob1 = Solution() print(ob1.isMajorityElement([2,4,5,5,5,5,5,6,6], 5))
ইনপুট
[2,4,5,5,5,5,5,6,6] 5
আউটপুট
true
