网站推广方法有几个,成都门户网站建设,网站怎么设置qq,百度快照 直接进入网站Leetcode 3048. Earliest Second to Mark Indices I 1. 解题思路2. 代码实现 题目链接#xff1a;3048. Earliest Second to Mark Indices I
1. 解题思路
这一题的话基础的思路就是二分法查找最小的可以将所有的数字都mark上的最小位置。
因此#xff0c;这里的问题就会变…Leetcode 3048. Earliest Second to Mark Indices I 1. 解题思路2. 代码实现 题目链接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)-1if idx -1:breaklast_index[v[idx]] nums[k]return last_indexdef is_possible(k):last_index get_last_index(k)if len(last_index) n:return Falsecnt 0for i in range(k1):if i not in last_index:cnt 1elif cnt last_index[i]:return Falseelse:cnt - last_index[i]return Trueif not is_possible(m-1):return -1i, j sum(nums) len(nums)-2, m-1while j-i1:k (ij)//2if is_possible(k):j kelse:i kreturn j1提交代码评测得到耗时135ms占用内存17.5MB。
