当前位置:网站首页>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.
边栏推荐
- QT implementation window gradually disappears qpropertyanimation+ progress bar
- (lightoj - 1236) pairs forming LCM (prime unique decomposition theorem)
- One hundred questions of image processing (11-20)
- ffmpeg命令行使用
- 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
- Market trend report, technological innovation and market forecast of China's double sided flexible printed circuit board (FPC)
- Tert butyl hydroquinone (TBHQ) Industry Research Report - market status analysis and development prospect forecast
- Spark独立集群动态上线下线Worker节点
- FLV格式详解
猜你喜欢
【锟斤拷】的故事:谈谈汉字编码和常用字符集
Installation and use of VMware Tools and open VM tools: solve the problems of incomplete screen and unable to transfer files of virtual machines
第一章 MapReduce概述
第7章 __consumer_offsets topic
Simply try the new amp model of deepfacelab (deepfake)
<li>圆点样式 list-style-type
第三章 MapReduce框架原理
Local visualization tools are connected to redis of Alibaba cloud CentOS server
js封装数组反转的方法--冯浩的博客
原生js实现全选和反选的功能 --冯浩的博客
随机推荐
Market trend report, technological innovation and market forecast of desktop electric tools in China
(POJ - 3186) treatments for the cows (interval DP)
Codeforces Round #799 (Div. 4)A~H
Raspberry pie 4b64 bit system installation miniconda (it took a few days to finally solve it)
300th weekly match - leetcode
Solve the single thread scheduling problem of intel12 generation core CPU (II)
Detailed explanation of FLV format
Li Kou: the 81st biweekly match
Sublime text code formatting operation
Research Report on market supply and demand and strategy of China's four seasons tent industry
Installation and configuration of MariaDB
Codeforces Round #803 (Div. 2)A~C
Double specific tyrosine phosphorylation regulated kinase 1A Industry Research Report - market status analysis and development prospect prediction
QT simulates mouse events and realizes clicking, double clicking, moving and dragging
Codeforces - 1526C1&&C2 - Potions
(lightoj - 1369) answering queries (thinking)
Click QT button to switch qlineedit focus (including code)
js封装数组反转的方法--冯浩的博客
The concept of spark independent cluster worker and executor
Base dice (dynamic programming + matrix fast power)