Kiểm tra số là phần tử chiếm ưu thế trong mảng đã sắp xếp Python

Giả sử có mảng nums được sắp xếp theo thứ tự không giảm, và một số target. Cần kiểm tra xem target có phải là phần tử chiếm ưu thế (majority element) hay không. Phần tử chiếm ưu thế là phần tử xuất hiện nhiều hơn N/2 lần trong mảng độ dài N. Ví dụ: [2,4,5,5,5,5,5,6,6] với target=5 cho kết quả true.

Để giải quyết, sử dụng hai hàm hỗ trợ lower() và upper():

• lower(arr, target): tìm chỉ số đầu tiên của target dùng binary search
• upper(arr, target): tìm chỉ số cuối cùng của target dùng binary search
• Hàm chính: u := upper(nums, target), l := lower(nums, target). Trả về true nếu u - l + 1 > len(nums)/2 và u != -1, ngược lại false

Ví dụ (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))

Đầu vào

[2, 4, 5, 5, 5, 5, 5, 6, 6] 5

Kết quả

True