जांचें कि क्या कोई संख्या पायथन में एक क्रमबद्ध सरणी में बहुसंख्यक तत्व है

मान लीजिए कि हमारे पास एक सरणी है, जिसे nums कहा जाता है और जिसे गैर-घटते क्रम में क्रमबद्ध किया जाता है, और एक संख्या लक्ष्य। हमें यह पता लगाना होगा कि क्या लक्ष्य बहुसंख्यक तत्व है। एक सरणी में बहुसंख्यक तत्व एक ऐसा तत्व है जो लंबाई N की एक सरणी में N/2 से अधिक बार दिखाई देता है। इसलिए यदि सरणी इस तरह है - [2,4,5,5,5,5,5,6,6] और लक्ष्य 5 है, तो आउटपुट सत्य है।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• दो सहायक मॉड्यूल होंगे, निचला () और ऊपरी ()। ये इस प्रकार हैं।
• निचला() दो तर्क सरणी गिरफ्तारी और लक्ष्य लेता है, वह है -
• निम्न:=0, उच्च:=गिरफ्तारी की लंबाई
• जबकि कम <उच्च −
  • मध्य :=निम्न + (उच्च-निम्न)/2
  • अगर गिरफ्तारी [मध्य] =लक्ष्य, तो उच्च =मध्य, अन्यथा निम्न =मध्य + 1
• गिरफ्तार होने पर उच्च वापसी करें [उच्च] =लक्ष्य, अन्यथा -1
• ऊपरी () दो तर्क सरणी गिरफ्तारी और लक्ष्य लेता है, वह है -
• निम्न =0, उच्च =गिरफ्तारी की लंबाई
• जबकि कम <उच्च −
  • मध्य =निम्न + (उच्च-निम्न)/2
  • अगर गिरफ्तारी [मध्य] =लक्ष्य, तो निम्न =मध्य, अन्यथा उच्च =मध्य - 1
• गिरफ्तारी होने पर कम वापसी करें [कम] =लक्ष्य, अन्यथा -1
• मुख्य कार्य इस प्रकार होगा -
• u :=ऊपरी(गिरफ्तारी, लक्ष्य)
• l :=निचला (गिरफ्तारी, लक्ष्य)
• सही लौटें, जब 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