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 <= 1001 <= arr[i] <= 1001 <= m <= 1002 <= k <= 100
Solution 1: Brute Force
Time complexity: O(nmk)
Space complexity: O(1)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
class Solution { public: bool containsPattern(vector<int>& arr, int m, int k) { const int n = arr.size(); for (int i = 0; i + m * k <= n; ++i) { bool valid = true; for (int j = 1; j < k && valid; ++j) for (int p = 0; p < m && valid; ++p) if (arr[i + j * m + p] != arr[i + p]) valid = false; if (valid) return true; } return false; } }; |
Solution 2: Shift and count
Since we need k consecutive subarrays, we can compare arr[i] with arr[i + m], if they are the same, increase the counter, otherwise reset the counter. If the counter reaches (k – 1) * m, it means we found k consecutive subarrays of length m.
ex1: arr = [1,2,4,4,4,4], m = 1, k = 3
i arr[i], arr[i + m] counter
0 1. 2. 0
0 2. 4. 0
0 4. 4. 1
0 4. 4. 2. <– found
ex2: arr = [1,2,1,2,1,1,1,3], m = 2, k = 2
i arr[i], arr[i + m] counter
0 1. 1. 1
0 2. 2. 2 <– found
Time complexity: O(n)
Space complexity: O(1)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
class Solution { public: bool containsPattern(vector<int>& arr, int m, int k) { const int n = arr.size(); int count = 0; for (int i = 0; i + m < n; ++i) { if (arr[i] == arr[i + m]) { if (++count == (k - 1) * m) return true; } else { count = 0; } } return false; } }; |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
huahualeetcode
Be First to Comment