网站制作公司-山而,望城经济建设开区门户网站,中国纪检监察报谁题的报名,自助模块化网站建设1、题目#xff1a;
对给定的有序数组 nums 删除重复元素#xff0c;在删除重复元素之后#xff0c;每个元素只出现一次#xff0c;并返回新的长度#xff0c;上述操作必须通过原地修改数组的方法#xff0c;使用 O(1) 的空间复杂度完成。 2、分析特点#xff1a;
题目… 1、题目
对给定的有序数组 nums 删除重复元素在删除重复元素之后每个元素只出现一次并返回新的长度上述操作必须通过原地修改数组的方法使用 O(1) 的空间复杂度完成。 2、分析特点
题目要求原地修改、 有序数组原地删除 结果数组一定比原数组的长度更短 并且我们可以 把结果数组直接写在原数组上 。有序数组 当前元素和前一个元素是相等的时候则不需要收集 我们需要收集的元素是那些不会等于前一个元素的充分利用有序的特点 继续往前遍历只要不等于前一个元素就可以收集起来等于了就放弃比如 2 3 3第一个 3 作为当前元素的时候和前一个元素不相等可以收集起来到了第二个 3 和前一个元素相等了放弃收集。 3、特点
有序数组剔除掉相等的拿当前位置的元素去和前一个元素比较 即if (nums[fast] ! nums[fast - 1]); 并且 0 位置的元素早就进入结果集需要看后面的元素是否进结果则定义的两个指针开始判断收集的起点下标从1开始。
定义两个指针 fast 和 slow 分别为快指针和慢指针
快指针表示遍历原数组到达的下标位置慢指针表示结果数组的下标位置即下一个不同元素要填入的下标位置初始时两个指针都指向下标 1。
快指针的范围是从 1 到 最后一个元素位置
慢指针是从 1 开始不断根据快指针满足了条件就加入收集结果(前提0位置的元素早就进入了结果需要看后面的元素是否进结果) 4、代码 public int removeDuplicates(int[] nums) {int n nums.length;if (n 0) {return 0;}int slow 1;for(int fast 1; fast n; fast){if (nums[fast] ! nums[fast - 1]) {nums[slow] nums[fast];slow;}}return slow;}5、复杂度分析 时间复杂度O(n)其中 n 是数组的长度。快指针和慢指针最多各移动 n 次。空间复杂度O(1)。只需要使用常数的额外空间。 6、总结
有序数组剔除掉相等的拿当前位置的元素去和前一个元素比较即if (nums[fast] ! nums[fast - 1]); 并且 0 位置的元素早就进入结果集需要看后面的元素是否进结果则定义的两个指针开始判断收集的起点下标从1开始。 如果本文对你有帮助的话记得给一乐点个赞哦感谢
