Leetcode 3048. Earliest Second to Mark Indices I
1. 解题思路
这一题的话基础的思路就是二分法查找最小的可以将所有的数字都mark上的最小位置。
因此，这里的问题就会变成如何快速地判断对于一个给定的位置，能否在这个操作序列下将所有的数字全部mark上。
而考虑的可能的操作，显然有：
- 要将一个数mark上，必须在某次操作时其给出的mark indice正好为这个位置，且之前已经将其减为0了。
因此，我们就要确保：
- 在对应的操作序列下所有的位置至少都出现过一次；
- 在最后一次出现某一位置的操作前，我们可以将对应位置上的值变为0；
因此，我们只需要对每一个长度的操作序列，判断其各个位置的操作是否齐全以及其最后一次操作的位置，然后分配一下decrease的顺序是否可以满足即可。
2. 代码实现
给出python代码实现如下：
class Solution:
def earliestSecondToMarkIndices(self, nums: List[int], changeIndices: List[int]) -> int:
n, m = len(nums), len(changeIndices)
changeIndices = [x-1 for x in changeIndices]
idxs = defaultdict(list)
for i, x in enumerate(changeIndices):
idxs[x].append(i)
def get_last_index(n):
last_index = {}
for k, v in idxs.items():
idx = bisect.bisect_right(v, n)-1
if idx == -1:
break
last_index[v[idx]] = nums[k]
return last_index
def is_possible(k):
last_index = get_last_index(k)
if len(last_index) < n:
return False
cnt = 0
for i in range(k+1):
if i not in last_index:
cnt += 1
elif cnt < last_index[i]:
return False
else:
cnt -= last_index[i]
return True
if not is_possible(m-1):
return -1
i, j = sum(nums) + len(nums)-2, m-1
while j-i>1:
k = (i+j)//2
if is_possible(k):
j = k
else:
i = k
return j+1
提交代码评测得到：耗时135ms，占用内存17.5MB。
原文地址：https://blog.csdn.net/codename_cys/article/details/136285471
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！