পাইথনে সর্টেড অ্যারেতে মেজরিটি এলিমেন্ট যাচাই করা

মনে করুন nums নামে একটি অ্যারে আছে যা নন-ডিক্রিজিং অর্ডারে সর্টেড, এবং একটি target নম্বর। আমাদের জানতে হবে target কি মেজরিটি এলিমেন্ট। একটি অ্যারেতে মেজরিটি এলিমেন্ট হল এমন একটি এলিমেন্ট যা অ্যারের দৈর্ঘ্য N-এ N/2-র চেয়ে বেশি বার উপস্থিত থাকে। যেমন অ্যারে [2,4,5,5,5,5,5,6,6] এবং target 5 হলে আউটপুট true।

এটি সমাধান করার জন্য আমরা নিচের ধাপগুলো অনুসরণ করব:

দুটি হেল্পার মডিউল থাকবে: lower() এবং upper()। এগুলো নিচের মতো।
lower() দুটি আর্গুমেন্ট নেয়: array arr এবং target
- low := 0, high := arr দৈর্ঘ্য
- যখন low < high
  - mid := low + (high - low)/2
  - যদি arr[mid] = target, high = mid, অন্যথায় low = mid + 1
- যদি arr[high] = target হলে high রিটার্ন করুন, অন্যথায় -1
upper() দুটি আর্গুমেন্ট নেয়: array arr এবং target
- low = 0, high = arr দৈর্ঘ্য
- যখন low < high
  - mid = low + (high - low)/2
  - যদি arr[mid] = target, low = mid, অন্যথায় high = mid - 1
- যদি arr[low] = target হলে low রিটার্ন করুন, অন্যথায় -1
মেইন ফাংশন
- u := upper(arr, target)
- l := lower(arr, target)
- true রিটার্ন করুন যদি u - l + 1 > len(nums)/2 এবং u != -1, অন্যথায় false

উদাহরণ (পাইথন)

নিচের ইমপ্লিমেন্টেশনটি দেখুন ভালো বুঝতে:

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