山西做网站的公司有哪些,重庆网站制作长沙,如何搭建购物平台,怎么创建自己的博客网站26.删除重复元素
题目描述
给你一个 非严格递增排列 的数组 nums #xff0c;请你 原地 删除重复出现的元素#xff0c;使每个元素 只出现一次 #xff0c;返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。
考虑 nums 的唯一元…26.删除重复元素
题目描述
给你一个 非严格递增排列 的数组 nums 请你 原地 删除重复出现的元素使每个元素 只出现一次 返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。
考虑 nums 的唯一元素的数量为 k 你需要做以下事情确保你的题解可以被通过
更改数组 nums 使 nums 的前 k 个元素包含唯一元素并按照它们最初在 nums 中出现的顺序排列。nums 的其余元素与nums 的大小不重要。 返回 k 。
解题思路
这类题目要学会不要第一时间想到for循环而是尝试使用双指针的方式。双指针的关键就是确定两个指针移动的时机。根据不同的移动时机和方向双指针可以分为快慢指针碰撞指针以及滑动窗口。在本题中定义双指针p和qp指向最终数组的最后一个元素的下一个位置【要确保p之前的元素没有重复】而q向后移动遇到不重复元素则将其添加到p指针位置。
理清思路就可以明确pq两个指针的移动时机
当q指向无重复元素时将该元素移动至p指针位置然后p向后移动一位q指针每一轮向后移动一位这种移动方式的双指针称为快慢指针。其中p为慢指针q为快指针。
代码
class Solution {public int removeDuplicates(int[] nums) {// 初始化int n nums.length;if (n 0) {return 0;}// 核心算法int fast 1, slow 1;while (fast n) {if (nums[fast] ! nums[fast - 1]) {// 当快指针遇到了不重复元素时将该元素放到慢指针的位置nums[slow] nums[fast];// 慢指针向后移动一位slow;}// 每一轮快指针都向后移动一位fast;}// 返回return slow;}
}
27.移除元素
题目描述
给你一个数组 nums 和一个值 val你需要 原地 移除所有数值等于 val 的元素并返回移除后数组的新长度。
不要使用额外的数组空间你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
解题思路
这题依旧是使用快慢指针。思路如下 定义快慢指针都指向第一个元素然后快指针开始遍历数组。若快指针指向的元素不等于val那么将该元素放到慢指针所指向的位置然后慢指针才向后移动一步。 理清思路后明确快慢指针的移动时机
快指针遍历数组每一轮都向后移动一位当快指针指向的元素不等于val时将快指针指向元素放到慢指针处慢指针向后移动一位
代码
class Solution {public int removeElement(int[] nums, int val) {int n nums.length;// 定义慢指针int slow 0;// 快指针遍历数组for (int fast 0; fast n; fast) {if (nums[fast] ! val) {// 若快指针指向的元素不等于val则将快指针的元素放到慢指针处nums[slow] nums[fast];// 这种情况下慢指针移动一步。slow;}}return slow;}
}
