当前位置:网站首页>LeetCode 1562. Find the latest group of size M
LeetCode 1562. Find the latest group of size M
2022-07-06 16:43:00 【Daylight629】
1562. Find size is M The latest group of
Medium difficulty 52 Switch to English to receive dynamic feedback
Give you an array arr
, This array represents a from 1
To n
Numerical arrangement of . There is a length of n
Binary string of , All bits on this string are initially set to 0
.
In from 1
To n
Every step of i
in ( Suppose binary strings and arr
from 1
Start indexing ), Binary string at position arr[i]
The bit of will be set to 1
.
Give you an integer m
, Please find out that the binary string has a length of m
A group of 1
The last step of . A group of 1
It's a continuous 、 from 1
Composed of substrings , And there are no longer extendable on the left and right 1
.
Return the existing length just by m
Of A group of 1
The last step of . If there is no such step , Please return -1
.
Example 1:
Input :arr = [3,5,1,2,4], m = 1
Output :4
explain :
step 1:"00100", from 1 A group of :["1"]
step 2:"00101", from 1 A group of :["1", "1"]
step 3:"10101", from 1 A group of :["1", "1", "1"]
step 4:"11101", from 1 A group of :["111", "1"]
step 5:"11111", from 1 A group of :["11111"]
The length of existence is 1 A group of 1 The last step of is step 4 .
Example 2:
Input :arr = [3,1,5,4,2], m = 2
Output :-1
explain :
step 1:"00100", from 1 A group of :["1"]
step 2:"10100", from 1 A group of :["1", "1"]
step 3:"10101", from 1 A group of :["1", "1", "1"]
step 4:"10111", from 1 A group of :["1", "111"]
step 5:"11111", from 1 A group of :["11111"]
No matter which step, it cannot form a length of 2 A group of 1 .
Example 3:
Input :arr = [1], m = 1
Output :1
Example 4:
Input :arr = [2,1], m = 2
Output :2
Tips :
n == arr.length
1 <= n <= 10^5
1 <= arr[i] <= n
arr
All integers in Different from each other1 <= m <= arr.length
Two 、 Method 1
simulation
class Solution {
public int findLatestStep(int[] arr, int m) {
int n = arr.length;
int[][] endpoints = new int[n + 1][2];
for (int i = 0; i <= n; i++) {
Arrays.fill(endpoints[i], -1);
}
int cnt = 0;
int ret = -1;
for (int i = 0; i < n; i++) {
int left = arr[i], right = arr[i];
if (arr[i] > 1 && endpoints[arr[i] - 1][0] != -1) {
left = endpoints[arr[i] - 1][0];
int leftLength = endpoints[arr[i] - 1][1] - endpoints[arr[i] - 1][0] + 1;
if (leftLength == m) {
cnt--;
}
}
if (arr[i] < n && endpoints[arr[i] + 1][1] != -1) {
right = endpoints[arr[i] + 1][1];
int rightLength = endpoints[arr[i] + 1][1] - endpoints[arr[i] + 1][0] + 1;
if (rightLength == m) {
cnt--;
}
}
int length = right - left + 1;
if (length == m) {
cnt++;
}
if (cnt > 0) {
ret = i + 1;
}
endpoints[left][0] = endpoints[right][0] = left;
endpoints[left][1] = endpoints[right][1] = right;
}
return ret;
}
}
Complexity analysis
Time complexity :O(n), among n Is the length of the array . When dealing with each step , We only visited the values of the left and right adjacent elements , Only the values at the left and right endpoints of the new group have been modified , Therefore, the time-consuming of each step is O(1) Of .
Spatial complexity :O(n). We need to open up an array with the same length as the original array endpoints.
边栏推荐
- Problem - 1646C. Factorials and Powers of Two - Codeforces
- Codeforces - 1526C1&&C2 - Potions
- Solve the single thread scheduling problem of intel12 generation core CPU (II)
- ffmpeg命令行使用
- Simple records of business system migration from Oracle to opengauss database
- China double brightening film (dbef) market trend report, technical dynamic innovation and market forecast
- Research Report of desktop clinical chemical analyzer industry - market status analysis and development prospect prediction
- 力扣leetcode第 280 场周赛
- 第6章 DataNode
- Codeforces Round #801 (Div. 2)A~C
猜你喜欢
One hundred questions of image processing (1-10)
It is forbidden to trigger onchange in antd upload beforeupload
Oneforall installation and use
Browser print margin, default / borderless, full 1 page A4
【锟斤拷】的故事:谈谈汉字编码和常用字符集
第三章 MapReduce框架原理
Log statistics (double pointer)
我在字节跳动「修电影」
Installation and use of VMware Tools and open VM tools: solve the problems of incomplete screen and unable to transfer files of virtual machines
SQL quick start
随机推荐
Li Kou: the 81st biweekly match
Hbuilder X格式化快捷键设置
Detailed explanation of FLV format
CMake速成
JS time function Daquan detailed explanation ----- AHAO blog
Click QT button to switch qlineedit focus (including code)
Problem - 1646C. Factorials and Powers of Two - Codeforces
Research Report on market supply and demand and strategy of double drum magnetic separator industry in China
300th weekly match - leetcode
Educational Codeforces Round 122 (Rated for Div. 2)
Calculate the time difference
QT implementation fillet window
SQL快速入门
It is forbidden to trigger onchange in antd upload beforeupload
Simple records of business system migration from Oracle to opengauss database
Date plus 1 day
Pull branch failed, fatal: 'origin/xxx' is not a commit and a branch 'xxx' cannot be created from it
Market trend report, technological innovation and market forecast of China's double sided flexible printed circuit board (FPC)
Codeforces Global Round 19
简单尝试DeepFaceLab(DeepFake)的新AMP模型