javascript算法之从会用到理解 - 双指针_js双指针算法

活动地址：CSDN21天学习挑战赛

目录

前言​

1.双指针

1.1 leecode题目-删除排序数组中的重复项

1.2 分解题目

1.3 解题思路

1.4 代码

1.5 复杂度分析

2. 个人常用方式

2.1 思路

2.2 代码

3. 总结

---

前言​

        为什么要说算法的从会用到理解？正如很多朋友一样，我们都是“成熟”的程序员了，惯用了各种依赖包，也就放弃了对算法的深究，所以处理各种实用场景信手拈来（哈哈，不要脸了），但是，最近在处理和思考优化方面的问题，深究之后，发现万变不离其宗，代码优化的一大部分工作还是要从算法上解决。

        趁此机会，也督促自己去深层理解理解算法的实质。

        算法的题目会来自leecode以及活动负责人的算法讲解。

1.双指针

1.1 leecode题目-删除排序数组中的重复项

给你一个 升序排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。

输入：nums = [1,1,2]
输出：2

1.2 分解题目

• 升序数组nums
• 原地修改，不允许新增数组
• 返回值为去重后的数组长度

1.3 解题思路

        由于数组nums为有序的升序数组，即存在重复的数据都是相邻的。所以我们只需要得到两个相邻元素不同的所有元素即可。此时我们就可以使用双指针来处理，设快指针为fast,慢指针为slow;

• 当nums长度为0时，数组无数据，返回值为0；
• 当nums长度为1时，数组只有一个元素，所以无重复值无需处理，返回值为1；
• 当nums长度大于1时，设数组的长度为length,快指针为fast=1,慢指针slow=1,遍历数组，当快指针小与数组长度时，判断两个相邻元素不相同，nums[fast] 不等于 nums[fase -1],不相同，则，将快指针的元素赋值给慢指针nums[slow] = nums[fast],同时慢指针slow加1;遍历结束，则慢指针slow即为去重后的数组长度；

1.4 代码

function uniq(nums) {
  let length = nums.length;
  if (length === 0) {
    return 0;
  }
  let fast = 1,
    slow = 1;
  while (fast < length) {
    if (nums[fast] !== nums[fast - 1]) {
      nums[slow] = nums[fast];
      ++slow;
    }
    ++fast;
  }
  return slow;
}
uniq([1, 1, 2]);

输出值为2；

1.5 复杂度分析

• 时间复杂度：O(n)，其中 n 是数组的长度。快指针和慢指针最多各移动 n 次。

• 空间复杂度：O(1)。只需要使用常数的额外空间。

2. 个人常用方式

        for循环倒序遍历，删除重复的数据；

2.1 思路

• 倒序遍历数组，
• 判断数组中当前元素第一次出现的索引是否等于当前索引，不相等，则证明当前元素在数组中存在第二个，所以，删除当前元素；此时数组长度减1，但是当下一次循环进入，索引减1，得到的元素，依旧是当前元素，可以继续判断当前元素是否有多余重复值；

2.2 代码

function uniq2(nums) {
  for (let i = nums.length - 1; i >= 0; --i) {
    if (nums.indexOf(nums[i]) !== i) nums.splice(i, 1);
  }
  return nums.length;
}
 
uniq2([1, 1, 2]);

        注意：千万不能使用正序for循环删除元素，如果是正序for循环，则会导致删除元素的下一个元素错过循环；

3. 总结

        for循环倒序遍历方法可以面对无序数组的处理或者其他字段的处理，但是我们也可以通过自己将数组变为有序数，将其改造为符合双指针操作的条件。

        一句老话：

只要思想不滑坡，方法总比困难多！

觉得有用的话，一键三连吧！点赞、收藏、评论！