मान लीजिए हमारे पास एक सरणी है जिसे nums कहा जाता है और यह गैर-घटते क्रम में क्रमबद्ध है, और एक संख्या target है। हमें यह पता लगाना है कि क्या target एक बहुमत तत्व है। एक सरणी में एक बहुमत तत्व वह तत्व है जो लंबाई N की सरणी में N/2 से अधिक बार प्रकट होता है। इसलिए यदि सरणी जैसी है - [2,4,5,5,5,5,5,6,6] और target 5 है, तो आउटपुट true है।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
- दो सहायक मॉड्यूल होंगे, lower() और upper()। ये इस प्रकार हैं।
- lower() दो तर्क लेता है सरणी arr और target, जो है -
- low := 0, high := arr की लंबाई
- जब low < high -
- mid := low + (high - low)/2
- यदि arr[mid] = target, तो high = mid, अन्यथा low = mid + 1
- high लौटाएं जब arr[high] = target, अन्यथा -1
- upper() दो तर्क लेता है सरणी arr और target, जो है -
- low = 0, high = arr की लंबाई
- जब low < high -
- mid = low + (high - low)/2
- यदि arr[mid] = target, तो low = mid, अन्यथा high = mid - 1
- low लौटाएं जब arr[low] = target, अन्यथा -1
- मुख्य फ़ंक्शन इस तरह होगा -
- u := upper(arr, target)
- l := lower(arr, target)
- यदि u -1 नहीं है तो u - l + 1 > (nums की लंबाई) / 2 होने पर true लौटाएं, अन्यथा false
उदाहरण (Python)
बेहतर समझ के लिए निम्न कार्यान्वयन देखें -
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