Python中检查数字是否为排序数组中的众数元素

假设我们有一个名为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
• 当 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 不为 -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

Arnab Chakraborty

更新于：2020年4月28日

257 次浏览

开启您的职业生涯

完成课程获得认证

开始学习