Leetcode 1562. Find Latest Group of Size M (python)

题目

解法1：TLE

自己开始想出来的非常复杂的解法，还是TLE了，主要T在从list里面删除元素

class Solution:def findLatestStep(self, arr: List[int], m: int) -> int:ans = -1pos2len = {
    }len2pos = collections.defaultdict(list)for i, num in enumerate(arr):tmp = 1left_len = pos2len[num-1] if num-1 in pos2len else 0right_len = pos2len[num+1] if num+1 in pos2len else 0tmp += left_lentmp += right_lenpos2len[num] = tmplen2pos[tmp].append(num)if left_len:for j in range(1,left_len+1):#print('j',j)pos2len[num-j] = tmplen2pos[left_len].remove(num-j)len2pos[tmp].append(num-j)if right_len:for j in range(1,right_len+1):pos2len[num+j] = tmplen2pos[right_len].remove(num+j)len2pos[tmp].append(num+j)#print(pos2len,len2pos)if len(len2pos[m])>0:ans = i+1return ans

解法2：

这道题其实感觉来看更像是个union find的问题，但是用union find好像过于复杂，这边找到了一种非常genious的做法。主体思想还是跟上一种解法是一样的，在某个位置插入的时候看左边的位置和右边的位置观察能不能连接起来，关键就在于想到其实这个时候符不符合条件不需要看完所有的位置，也不需要更新左边子串和右边子串的所有的位置，而是只需要更新边界：

class Solution:def findLatestStep(self, arr: List[int], m: int) -> int:n = len(arr)if n==m:return nlength_list = [0]*(n+2)res = -1for i,num in enumerate(arr):# find the length of contiguous substring of 1s on teh left and rightleft = length_list[num-1]right = length_list[num+1]# update the two boundary position of the new contiguous substring of 1s any position that is inside this substring doesn't matterlength_list[num-left] = length_list[num+right] = left+right+1# Notive that for this operation, we will only influence the substring on the left and subdtring on the right. The other substrings remain the same. So if left or right has substring that statisfy condition, which means the last operation (i-1 th operation) is still valid. Since the operation is 1 indexed, we update the results as iif left==m or right==m:res = ireturn res

参考：
https://leetcode.com/problems/find-latest-group-of-size-m/discuss/836441/Very-Easy
https://leetcode.com/problems/find-latest-group-of-size-m/discuss/891842/C%2B%2B-O(N)-Easy-to-UnderStand-Comment-for-Doubts