在 Python 中检查数字是否是已排序数组中的多数元素

pythonserver side programmingprogramming更新于 2025/10/26 19:24:17

假设我们有一个名为 nums 的数组，该数组按非递减顺序排序，并且有一个数字目标。我们必须确定目标是否是多数元素。在数组中，多数元素是在长度为 N 的数组中出现超过 N/2 次的元素。因此，如果数组类似于 − [2,4,5,5,5,5,5,6,6] 且目标是 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
当 arr[high] = target 时返回 high，否则返回 -1
upper() 接受两个参数数组 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)
当 u – l + 1 > (length of nums) / 2 时，如果 u 不为 -1，则返回 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))