目录
一、数组理论基础
二、快慢指针法(双指针法)
三、相关算法题目
四、遇到的问题
一、数组理论基础
数组是存放在连续内存空间上的相同类型数据的集合。
代码随想录 (programmercarl.com)
特点:
1.下标从0开始,内存中的地址空间是连续的
2.查询快,增删慢
3.二维数组中,行为第一索引,列为第二索引
二、快慢指针法(双指针法)
思想:通过一个快指针和慢指针在一个for循环下完成两个for循环的工作。
定义快慢指针,通常快指针用来遍历整个数组,寻找要求的新数组元素,慢指针用来指向新数组的下标。
三、相关算法题目
1.27.移除元素
27. 移除元素 - 力扣(LeetCode)
快指针:寻找新数组元素(新数组即不包含目标元素的数组
慢指针:指向新数组下标的位置
四种解法:
暴力法:双重for循环
class Solution {public int removeElement(int[] nums, int val) { //暴力法int len = nums.length;for(int i = 0;i < len;i++){if(nums[i] == val){for(int j = i;j < len - 1;j++){nums[j] = nums[j+1];//j的取值要理解 //右边的取值要能够取到最后一个元素的值 //即 nums[size-1] 或者 < size}len--;i--; //容易忘记⭐️}}return len;
}
}
双指针法
class Solution {public int removeElement(int[] nums, int val) {//双指针解法int slowIndex = 0;for(int fastIndex = 0;fastIndex < nums.length;fastIndex++){if(nums[fastIndex] != val){nums[slowIndex] = nums[fastIndex];slowIndex++;}}return slowIndex;
}
}
相向指针法(两种判断条件)
class Solution {public int removeElement(int[] nums, int val) {//相向双指针法 一头一尾两个指针int left = 0;int right = nums.length -1;while(left <= right){if(nums[left] == val){nums[left] = nums[right];right--; //这里left不动 //因为要考虑换过去的right的值是否等于val}else{left++;}}return left;//相向双指针法 一头一尾两个指针 法2int left = 0;int right = nums.length - 1;while(right >= 0 && nums[right] == val) right--;while(left <= right){if(nums[left] == val){nums[left] = nums[right];right--;}left++;while(right >= 0 && nums[right] == val) right--;//为了保证换过去的right值 不等于val }return left;
}
}
2.26.删除有序数组中的重复项
26. 删除有序数组中的重复项 - 力扣(LeetCode)
快指针: 遍历原数组,寻找新数组元素(新数组即没有重复元素的数组)
慢指针:下一个不同元素要填入的下标位置
解法:双指针法
class Solution {public int removeDuplicates(int[] nums) {//快慢指针int slow = 0;int len = nums.length;int val = nums[0];for(int fast = 1;fast < len;fast++){if(nums[fast] != val){//也可以不设置变量 val,直接比较 nums[fast]和nums[fast-1]val = nums[fast];nums[++slow] = nums[fast];}}return slow + 1;}
}
四、遇到的问题
暴力法一开始思路不对,快慢指针没思路,不了解该方法。。。
27.移除元素中
1.暴力法
for(int j = i + 1;j < len;j++){
nums[j-1] = nums[j];//j的取值要理解,右边的取值要能够取到最后一个元素的值,即 nums[size-1] 或者 < size
for(int j = i;j < len - 1;j++)
nums[j] = nums[j+1];// 这种写法也对
2. i--; //容易忘记⭐️,当前i对应的数组值 是后面移动过来的 还未进行判断的值,这里-1是为了在外层循环+1后,仍然使 i 指向当前还未判断的第一个值;
3.双向指针法 两种写法,区别在于是否考虑 换过去的right值 是否等于val,从而决定 left++ 写在什么位置 即if-else条件句的不同;
26.删除有序数组中的重复项中
1.快慢指针法,也可以不设置变量 val,直接比较 nums[fast]和nums[fast-1]。