ตรวจสอบว่าตัวเลขเป็นองค์ประกอบส่วนใหญ่ในอาร์เรย์ที่เรียงลำดับใน Python หรือไม่

สมมติว่าเรามีอาร์เรย์ที่เรียกว่า nums และเรียงลำดับแบบไม่ลดจำนวนและเป้าหมายตัวเลข เราต้องค้นหาว่าเป้าหมายเป็นองค์ประกอบส่วนใหญ่หรือไม่ ในอาร์เรย์ องค์ประกอบส่วนใหญ่คือองค์ประกอบที่ปรากฏมากกว่า N/2 ครั้งในอาร์เรย์ที่มีความยาว N ดังนั้นหากอาร์เรย์มีลักษณะเช่นนี้ − [2,4,5,5,5,5,5,6,6] และเป้าหมายคือ 5 จากนั้นผลลัพธ์จะเป็นจริง

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• จะมีโมดูลช่วยเหลืออยู่ 2 โมดูล คือ lower() และ upper() มีดังต่อไปนี้
• ตัวล่าง() รับสองอาร์กิวเมนต์อาร์เรย์ arr และเป้าหมาย นั่นคือ −
• ต่ำ :=0, สูง :=ความยาวของ arr
• ในขณะที่ต่ำ <สูง −
  • กลาง :=ต่ำ + (สูง - ต่ำ)/2
  • ถ้า arr[กลาง] =เป้าหมาย แล้วสูง =กลาง มิฉะนั้น ต่ำ =กลาง + 1
• ผลตอบแทนสูงเมื่อ arr[high] =เป้าหมาย มิฉะนั้น -1
• ตัวบน () รับสองอาร์กิวเมนต์อาร์เรย์ arr และเป้าหมาย นั่นคือ −
• ต่ำ =0, สูง =ความยาวของ arr
• ในขณะที่ต่ำ <สูง −
  • กลาง =ต่ำ + (สูง - ต่ำ)/2
  • ถ้า arr[กลาง] =เป้าหมาย แล้วต่ำ =กลาง มิฉะนั้น สูง =กลาง - 1
• ผลตอบแทนต่ำเมื่อ arr[low] =เป้าหมาย มิฉะนั้น -1
• หน้าที่หลักจะเป็นเช่น −
• u :=upper(arr, target)
• l :=ต่ำกว่า (arr, เป้าหมาย)
• คืนค่า จริง เมื่อ u – l + 1> (ความยาวของ nums) / 2 ถ้าคุณไม่ใช่ -1 มิฉะนั้น จะเป็นเท็จ

ตัวอย่าง(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