สมมติว่าเรามีอาร์เรย์ชื่อ nums ที่เรียงในลำดับไม่ลดลง และตัวเลข target เราต้องตรวจสอบว่า target เป็น majority element หรือไม่ ในอาร์เรย์ majority element คือองค์ประกอบที่ปรากฏมากกว่า N/2 ครั้งในอาร์เรย์ที่มีความยาว N ดังนั้นถ้าอาร์เรย์คือ [2,4,5,5,5,5,5,6,6] และ target คือ 5 ผลลัพธ์คือ true
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนต่อไปนี้ −
- จะมีโมดูลช่วยสองตัวคือ lower() และ upper() รายละเอียดดังนี้
- lower() รับสองอาร์กิวเมนต์ คืออาร์เรย์ arr และ target −
- low := 0, high := ความยาวของ arr
- while 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
- while 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)
- คืนค่า true เมื่อ u - l + 1 > (ความยาวของ nums) / 2 ถ้า u ไม่ใช่ -1 มิฉะนั้น 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
