Algorithms to Detect Pattern of Length M Repeated K or More Time
- 时间:2020-09-07 12:03:44
- 分类:网络文摘
- 阅读:94 次
Given an array of positive integers arr, find a pattern of length m that is repeated k or more times.
A pattern is a subarray (consecutive sub-sequence) that consists of one or more values, repeated multiple times consecutively without overlapping. A pattern is defined by its length and the number of repetitions.
Return true if there exists a pattern of length m that is repeated k or more times, otherwise return false.
Example 1:
Input: arr = [1,2,4,4,4,4], m = 1, k = 3
Output: true
Explanation: The pattern (4) of length 1 is repeated 4 consecutive times. Notice that pattern can be repeated k or more times but not less.Example 2:
Input: arr = [1,2,1,2,1,1,1,3], m = 2, k = 2
Output: true
Explanation: The pattern (1,2) of length 2 is repeated 2 consecutive times. Another valid pattern (2,1) is also repeated 2 times.Example 3:
Input: arr = [1,2,1,2,1,3], m = 2, k = 3
Output: false
Explanation: The pattern (1,2) is of length 2 but is repeated only 2 times. There is no pattern of length 2 that is repeated 3 or more times.Example 4:
Input: arr = [1,2,3,1,2], m = 2, k = 2
Output: false
Explanation: Notice that the pattern (1,2) exists twice but not consecutively, so it doesn’t count.Example 5:
Input: arr = [2,2,2,2], m = 2, k = 3
Output: false
Explanation: The only pattern of length 2 is (2,2) however it’s repeated only twice. Notice that we do not count overlapping repetitions.Constraints:
2 <= arr.length <= 100
1 <= arr[i] <= 100
1 <= m <= 100
2 <= k <= 100
Bruteforce Algorithm to Determine the Repeative String Pattern
Given the m and k are only less than 100 – we can totally do bruteforce algorithm. First loop the start index of the first pattern – then, we know the first pattern looks like – and we can construct k such patterns – and see if it equals to the sub array of the string.
The following bruteforce implemented in Python has O(N^2) time complexity.
1 2 3 4 5 6 7 8 | class Solution: def containsPattern(self, arr: List[int], m: int, k: int) -> bool: L = len(arr) for i in range(L - m * k + 1): p = arr[i:i+m]*k if p == arr[i:i+m*k]: return True return False |
class Solution: def containsPattern(self, arr: List[int], m: int, k: int) -> bool: L = len(arr) for i in range(L - m * k + 1): p = arr[i:i+m]*k if p == arr[i:i+m*k]: return True return False
Better Bruteforce Algorithm to Detect Pattern of Length M Repeated K or More Times
We can do this in a better way. We can check if the value at index i and index i + m equals – and increment the counter. If the counter equals (k-1)*m then we have k times of m-size pattern.
1 2 3 4 5 6 7 8 9 10 11 12 | class Solution: def containsPattern(self, arr: List[int], m: int, k: int) -> bool: L = len(arr) cnt = 0 for i in range(L - m): if arr[i] == arr[i + m]: cnt += 1 else: cnt = 0 if cnt == m * (k - 1): return True return False |
class Solution: def containsPattern(self, arr: List[int], m: int, k: int) -> bool: L = len(arr) cnt = 0 for i in range(L - m): if arr[i] == arr[i + m]: cnt += 1 else: cnt = 0 if cnt == m * (k - 1): return True return False
The complexity is O(N).
–EOF (The Ultimate Computing & Technology Blog) —
推荐阅读:Emerging Social Media Tools for Bloggers 2017 The Current State of Content Marketing [Infographic] How Facebook Can Build Or Destroy An Entrepreneur’s Career Top 3 Email Marketing Software for Turning Subscribers Into Cust Five Reasons to Get Business Funding for Your Blog How to Compute the Surface Area of 3D Shapes (Cubes Placed on Gr How to Find the Longest Harmonious Subsequence? How to Find the Length of Longest Fibonacci Subsequence using Br How to Find the Length of the Longest Increasing Subsequence usi Facing Heads Probabilties of Tossing Strange Coins using Dynamic
- 评论列表
-
- 添加评论