Kiểm tra xem một số có phải là phần tử đa số trong một mảng đã sắp xếp bằng Python hay không

Giả sử chúng ta có một mảng được gọi, nums và được sắp xếp theo thứ tự không giảm và mục tiêu là số. Chúng ta phải tìm xem mục tiêu có phải là yếu tố đa số hay không. Trong một mảng, phần tử đa số là phần tử xuất hiện nhiều hơn N / 2 lần trong một mảng có độ dài N. Vì vậy, nếu mảng giống như - [2,4,5,5,5,5,5,5,6,6] và mục tiêu là 5, thì kết quả đầu ra là true.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Sẽ có hai mô-đun trợ giúp, dưới () và trên (). Những điều này như sau.
• Phần dưới () nhận hai đối số là mảng arr và target, nghĩa là -
• low:=0, high:=length of arr
• trong khi thấp
• giữa:=low + (cao - thấp) / 2
• nếu arr [mid] =target thì high =mid, ngược lại low =mid + 1

Ví dụ (Python)

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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))

Đầu vào

[2,4,5,5,5,5,5,6,6]
5

Đầu ra

true