Re: [閒聊] 每日LeetCode
※ 引述《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
推
12/11 14:04,
2年前
, 1F
12/11 14:04, 1F
推
12/11 14:05,
2年前
, 2F
12/11 14:05, 2F
推
12/11 14:06,
2年前
, 3F
12/11 14:06, 3F
推
12/11 16:57,
2年前
, 4F
12/11 16:57, 4F
推
12/11 18:16,
2年前
, 5F
12/11 18:16, 5F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 573 之 719 篇)：