当前位置:网站首页>Array - fast and slow pointer in one breath
Array - fast and slow pointer in one breath
2022-06-25 02:48:00 【xicheng】
Preface
The last article talked about differential arrays , This article begins with the fast and slow pointer technique of the double pointer technique . in addition , The array has the following knowledge points and skills . 
Ideas
Manipulate an array with two pointers , Usually used in :1. When there are changes to the array and a new array cannot be created .2. A traversal of the implementation requirements .
in addition , Double pointer types have fast and slow pointers , Left and right pointer , Sliding window , Common type .
Speed pointer template
int Slow pointer = 0;
for (int Quick pointer = 0; fast < nums.length; Quick pointer ++) {
if ( The fast pointer satisfies a condition ) {
Slow pointer assignment operation
Slow pointer right movement operation
}
}
Remove duplicate items from an ordered array
leetcode The first 26 topic 
Their thinking
Apply template ,“ The fast pointer satisfies one of the conditions ”: The speed pointer refers to different elements . When the last value is returned , Need to set the slow pointer +1.
Complexity analysis
Time complexity :O(n),n Is the length of the array . Spatial complexity :O(1).
Code
class Solution {
public int removeDuplicates(int[] nums) {
int slow = 0;
for (int fast = 0; fast < nums.length; fast++) {
// The element indicated by the speed pointer does not work
if (nums[fast] != nums[slow]) {
nums[++slow] = nums[fast];
}
}
return slow + 1;
}
}
Remove elements
leetcode The first 27 topic 
Their thinking
Apply template ,“ The fast pointer satisfies one of the conditions ”: Indicates that the element indicated by the fast pointer is different from the given value .
Complexity analysis
Time complexity :O(n),n Is the length of the array .
Spatial complexity :O(1).
Code
class Solution {
public int removeElement(int[] nums, int val) {
int slow = 0;
for (int fast = 0; fast < nums.length; fast++) {
// The element indicated by the fast pointer is related to val Different
if (nums[fast] != val) {
nums[slow] = nums[fast];
slow++;
}
}
return slow;
}
}
Move zero
leetcode The first 283 topic
Their thinking
Apply template ,“ The fast pointer satisfies one of the conditions ”: The element indicated by the fast pointer is not equal to 0.
Finally, we traverse the array from the slow pointer , Assign values to all elements traversed 0.
Complexity analysis
Time complexity :O(n),n Is the length of the array .
Spatial complexity :O(1).
Code
class Solution {
public void moveZeroes(int[] nums) {
int slow = 0;
for (int fast = 0; fast < nums.length; fast++) {
if (nums[fast] != 0) {
nums[slow] = nums[fast];
slow++;
}
}
// Assign the full pointer and the following position to 0
for (int i = slow; i < nums.length; i++) {
nums[i] = 0;
}
}
}
ending
The speed pointer of the array is relatively simple , In addition, linked lists also have fast and slow pointer skills . The next algorithm article talks about the left and right pointers of double pointers .
Wechat scan the QR code below , Or search for “xicheng”, Pay attention to the official account 【 note 】, I have prepared 15 swastika Java Interview notes .
Thank you for your praise 、 Collections and reviews , Dry goods articles are continuously updated , See you in the next article !
边栏推荐
- Qt中使用QDomDocument操作XML文件
- Centos7.3 modifying MySQL default password_ Explain centos7 modifying the password of the specified user in MySQL
- PyTorch学习笔记(七)------------------ Vision Transformer
- 都2022年了,你还不了解什么是性能测试?
- ProcessOn制作ER过程(自定义)
- MySQL command backup
- Refresh mechanism of vie
- 对进程内存的实践和思考
- vie的刷新机制
- ACM. HJ70 矩阵乘法计算量估算 ●●
猜你喜欢

折叠屏将成国产手机分食苹果市场的重要武器

UnityShader入门精要——表面着色器

3 years of testing experience. I don't even understand what I really need on my resume. I need 20K to open my mouth?

I've been doing software testing for two years. I'd like to give some advice to girls who are still hesitating

【STL源码剖析】STL六大组件功能与运用(目录)

【STL源码剖析】配置器(待补充)

MATLAB主窗口与编辑器窗口分开为两个界面的解决办法

Yarn: unable to load file c:\users\xxx\appdata\roaming\npm\yarn PS1 because running scripts is prohibited on this system

計網 | 【四 網絡層】知識點及例題

Are programmers from Huawei, Alibaba and other large manufacturers really easy to find?
随机推荐
怎么开户打新债 开户是安全的吗
PSQL column to row
Processon producer process (customized)
Can the polardb database be connected to the data source through MySQL
[I.MX6UL] U-Boot移植(六) 网络驱动修改 LAN8720A
打新债100%中签的方法 开户是安全的吗
GO同步等待组
ACM. HJ70 矩阵乘法计算量估算 ●●
14 bs对象.节点名称.name attrs string 获取节点名称 属性 内容
Using qdomdocument to manipulate XML files in QT
UnityShader入门精要——PBS基于物理的渲染
ida中交叉引用的解析
Uncaught Error: [About] is not a <Route> component. All component children of <Routes> must be a <Ro
Of the seven levels of software testers, it is said that only 1% can achieve level 7
Summary of stack frame in arm assembly
Can automate - 10k, can automate - 20K, do you understand automated testing?
【STL源码剖析】STL六大组件功能与运用(目录)
How transformers Roberta adds tokens
yarn : 无法加载文件 C:\Users\xxx\AppData\Roaming\npm\yarn.ps1,因为在此系统上禁止运行脚本
Application of TSDB in civil aircraft industry
