資料結構
網路
關係資料庫管理系統(RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學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
更新於：2020年4月28日
257 次瀏覽
廣告