Tìm phần tử đỉnh trong Python

Giả sử chúng ta phải tìm phần tử đỉnh trong một mảng. Phần tử đỉnh là phần tử lớn hơn các phần tử lân cận của nó. Giả sử chúng ta có một nums mảng đầu vào, trong đó nums [i] ≠ nums [i + 1], tìm kiếm phần tử đỉnh và trả về chỉ số của nó. Mảng có thể chứa nhiều phần tử đỉnh, trong trường hợp đó, trả về chỉ số cho bất kỳ phần tử nào trong số các phần tử đỉnh. Chúng ta có thể tưởng tượng rằng nums [-1] =nums [n] =-∞. Vì vậy, nếu mảng giống như [1,2,1,3,5,6,4], các phần tử đỉnh phải là 1 hoặc 5.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• low:=0 và high:=chỉ số cuối cùng của mảng, n:=kích thước của mảng, ans:=infinity
• trong khi thấp <=cao
  • giữa:=low + (cao - thấp) / 2
  • nếu mid - 1> =0 và nums [mid - 1] <=nums [mid] thì low:=mid, ngược lại high:=mid - 1
• trả về mức thấp

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

class Solution(object):
   def findPeakElement(self, nums):
      low = 0
      high = len(nums)-1
      while low<high:
         mid = low + (high - low+1)//2
         if (mid-1>=0 and nums[mid-1]<=nums[mid]):
            low = mid
         else:
            high = mid-1
      return nums[low+1]
ob1 = Solution()
print(ob1.findPeakElement([15,35,85,96,5,6,8,12]))

Đầu vào

[15,35,85,96,5,6,8,12]

Đầu ra

5