粗略参考了答案,使用二分法,题目要求最大值
nums =[9,2,5,4]
,要是使用单纯的双重循环会让2与4配对,5与9无法配对。答案就只有2个标记,然而实际需要使用二分法2与5,4与9配对。答案为4.
from typing import List
class Solution:
def maxNumOfMarkedIndices(self, nums: List[int]) -> int:
nums_asc = sorted(nums)
res = 0
j_sign = len(nums_asc)//2
for i in range(len(nums_asc)//2):
for j in range(j_sign, len(nums_asc)):
j_sign = j + 1
if nums_asc[i] * 2 <= nums_asc[j]:
res += 2
break
if j_sign >= len(nums_asc):
break
return res```