推 sustainer123: 大師 12/11 14:04
推 JIWP: 大師 12/11 14:05
推 RinNoKareshi: 大師 12/11 14:06
推 pandix: 大師 12/11 16:57
推 NTHUlagka: 大師 12/11 18:16
※ 引述《Rushia (みけねこ的鼻屎)》之銘言：
: https://leetcode.com/problems/element-appearing-more-than-25-in-sorted-array
: 1287. Element Appearing More Than 25% In Sorted Array
: 給你一個有序的數字陣列，找出該數字陣列出現次數超過元素數量25%的元素是哪個，
: 題目保證恰好一解。
雖然是easy不過看到題目突然想到一個解
保證恰好一個數字超過25%
所以答案必然是len*1/4 len*2/4 len*3/4其中一個
所以拿這三個值去各二分搜兩次找上下界就可以得到區間
這樣複雜度就是logn了
心情好還可以前面再做幾個特判加速
然而題目length <= 10^4
搞一大串搞不好還比較慢
==
再多兩個0不知道看不看得出差距
import bisect
class Solution:
def findSpecialInteger(self, arr: List[int]) -> int:
l = len(arr)
q = l//4
if arr[0] == arr[q]:
return arr[0]
if arr[-1] == arr[-1-q]:
return arr[-1]
candidate = [arr[q], arr[l//2], arr[l*3//4]]
for i in range(2):
if candidate[i] == candidate[i+1]:
return candidate[i]
for c in candidate:
if bisect.bisect(arr, c) - bisect.bisect_left(arr, c) > q:
return c
--
你跟我說這個 我有什麼辦法
https://i.imgur.com/ns9RZkO.jpg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 203.67.131.72 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1702274617.A.420.html