当前位置:网站首页>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.
边栏推荐
- 两个礼拜速成软考中级软件设计师经验
- Two weeks' experience of intermediate software designer in the crash soft exam
- (lightoj - 1370) Bi shoe and phi shoe (Euler function tabulation)
- QT style settings of qcobobox controls (rounded corners, drop-down boxes, up expansion, editable, internal layout, etc.)
- 第5章 消费者组详解
- (POJ - 1458) common subsequence (longest common subsequence)
- Acwing: Game 58 of the week
- 视频压缩编码和音频压缩编码基本原理
- 本地可视化工具连接阿里云centOS服务器的redis
- 业务系统兼容数据库Oracle/PostgreSQL(openGauss)/MySQL的琐事
猜你喜欢
Hbuilder X格式化快捷键设置
第7章 __consumer_offsets topic
Spark独立集群动态上线下线Worker节点
QT implementation window gradually disappears qpropertyanimation+ progress bar
第6章 DataNode
第五章 Yarn资源调度器
原生js实现全选和反选的功能 --冯浩的博客
QT implementation fillet window
Discussion on QWidget code setting style sheet
Browser print margin, default / borderless, full 1 page A4
随机推荐
Sublime text code formatting operation
Spark independent cluster dynamic online and offline worker node
SQL quick start
Summary of FTP function implemented by qnetworkaccessmanager
SF smart logistics Campus Technology Challenge (no T4)
Story of [Kun Jintong]: talk about Chinese character coding and common character sets
Acwing: Game 58 of the week
js时间函数大全 详细的讲解 -----阿浩博客
Ffmpeg command line use
顺丰科技智慧物流校园技术挑战赛(无t4)
875. Leetcode, a banana lover
Advancedinstaller installation package custom action open file
JS encapsulates the method of array inversion -- Feng Hao's blog
Problem - 922D、Robot Vacuum Cleaner - Codeforces
(lightoj - 1369) answering queries (thinking)
Kubernetes cluster deployment
js封装数组反转的方法--冯浩的博客
Browser print margin, default / borderless, full 1 page A4
(POJ - 3186) treatments for the cows (interval DP)
Classic application of stack -- bracket matching problem