算法-数组：移除元素

你的名字 2023-09-28 13:39 21阅读 0赞

####  ####

*  前言
 *  移除元素
 *   *  思路
     *  图解
 *  相关题目
 *   *  26.删除排序数组中的重复项
     *   *  思路
         *  代码
     *  283.移动零
     *  977有序数组的平方
     *   *  思路
         *  代码
     *  844比较含退格的字符串
     *   *  思路
         *  代码

## 前言 ##

> **我们都知道数据结构和算法很重要，而且在校招和社招中，是必考的点，很多公司一上来就是手撕算法题，由此可以看出算法的重要性。我之前也做过一些算法题目，但是没有系统总结，而且没有坚持下来，总是断断续续的，希望从现在开始能养成习惯，每天坚持做题。我是决定跟着卡哥的路线来刷题，中间如果遇到一些不熟悉的数据结构的话，我还会去补补基础。**

接下来大家可以先看看本篇文章刷了哪些题  
![在这里插入图片描述][a340207bc99c48538c082364ae189b01.png]

## 移除元素 ##

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。

不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并**原地**修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

示例 1: 给定 nums = \[3,2,2,3\], val = 3, 函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。 你**不需要考虑数组中超出新长度后面的元素。**

示例 2: 给定 nums = \[0,1,2,2,3,0,4,2\], val = 2, 函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。

你不需要考虑数组中超出新长度后面的元素。  
[27. 移除元素][27.]

### 思路 ###

**使用快慢指针**

*  快指针：寻找新数组元素，新数组就是不含有目标元素的数组
 *  慢指针：指向更新新数组下标的位置  
    代码

class Solution {
        
        public int removeElement(int[] nums, int val) {
        
             //快慢指针
            int slow=0;
            int fast;
            for (fast=0;fast<nums.length;fast++){
        
                if (nums[fast]==val){
        
                    continue;
                }else{
        
                    nums[slow]=nums[fast];
                    slow++;
                }
            }
            return slow;
    
        }
    }

### 图解 ###

![在这里插入图片描述][f0fabd9acb304015afbf5af26fc2efa4.png]  
![在这里插入图片描述][5a05532f6cde442ca8f01d3679d38a9b.png]  
![在这里插入图片描述][324f034df5494b2c9cd7f1a62a867eb7.png]  
![在这里插入图片描述][a6f126625d054eda84aba0b2da26d57b.png]  
![在这里插入图片描述][23543891f9be42a4a2735ac07c2b02f2.png]

## 相关题目 ##

### 26.删除排序数组中的重复项 ###

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

由于在某些语言中不能改变数组的长度，所以必须将结果放在数组nums的第一部分。更规范地说，如果在删除重复项之后有 k 个元素，那么 nums 的前 k 个元素应该保存最终结果。

将最终结果插入 nums 的前 k 个位置后返回 k 。

不要使用额外的空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

示例 1：

输入：nums = \[1,1,2\]  
输出：2, nums = \[1,2,\_\]  
解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。  
示例 2：

输入：nums = \[0,0,1,1,1,2,2,3,3,4\]  
输出：5, nums = \[0,1,2,3,4\]  
解释：函数应该返回新的长度 5 ， 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。

提示：

1 <= nums.length <= 3 \* 104  
\-104 <= nums\[i\] <= 104  
nums 已按 升序 排列

#### 思路 ####

*  题目已知是升序
 *  使用快慢指针，如果有重复，肯定是和相邻元素比较
 *  当快指针指向元素和慢指针指向元素相等时，就让快指针后移，因为可能存在连续多个重复的元素
 *  当快指针指向元素和慢指针指向元素不同时，就让慢指针后移，然后让快指针指向的元素值赋值给慢指针指向位置

#### 代码 ####

class Solution {
        
        public int removeDuplicates(int[] nums) {
        
              //快慢指针，如果有重复，肯定是和相邻元素比较
            int slow=0;
            int fast;
            for (fast=1;fast<nums.length;fast++){
        
                 if (nums[fast]!=nums[slow]){
        
                     nums[++slow]=nums[fast];
                 }
            }
    
            return slow+1;
        }
    }

### 283.移动零 ###

链接[https://leetcode.cn/problems/move-zeroes/][https_leetcode.cn_problems_move-zeroes]  
![在这里插入图片描述][769ad42caa814b84ba741c04f75df432.png]

### 977有序数组的平方 ###

[977.有序数组的平方][977.]  
给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。  
示例 1：

输入：nums = \[-4,-1,0,3,10\]  
输出：\[0,1,9,16,100\]  
解释：平方后，数组变为 \[16,1,0,9,100\]  
排序后，数组变为 \[0,1,9,16,100\]  
示例 2：

输入：nums = \[-7,-3,2,3,11\]  
输出：\[4,9,9,49,121\]

提示：

1 <= nums.length <= 104  
\-104 <= nums\[i\] <= 104  
nums 已按 非递减顺序 排序

进阶：

请你设计时间复杂度为 O(n) 的算法解决本问题

#### 思路 ####

*  数组是递增的
 *  因为符号的原因所以，我们不能确定它们平方后绝对值的大小关系，不过，我们知道对于负数来说，如果它的平方比较大，那么它应该排在前面，如果是整数则排在后面
 *  我们通过双指针，一个指向头，一个指向尾，然后额外使用一个数组空间即可

#### 代码 ####

class Solution {
        
        public int[] sortedSquares(int[] nums) {
        
             /**
             * 递增排列
             * 前面的负数中绝对值大的
             * 后面的是正数中绝对值大的
             * 对它们进行比较就可以了
             * 双指针
             */
            int left=0;
            int right=nums.length-1;
            int[]ans=new int[nums.length];
            int index=right;
            while (left<=right){
        
                if (Math.abs(nums[left])<Math.abs(nums[right])){
        
                    //说明左边的绝对值小
                    ans[index]=nums[right]*nums[right];
                    right--;
                }else{
        
                    //说明左边大
                     ans[index]=nums[left]*nums[left];
                     left++;
                }
                index--;
            }
            return ans;
        }
    }

### 844比较含退格的字符串 ###

[题目链接][Link 2]

#### 思路 ####

*  如果扫描到\#则要把前一个字符覆盖
 *  使用快慢指针
 *  如果快指针指向的是\#，慢指针指向的不是0，则慢指针前移
 *  如果快指针指向的不是\#,则把快指针指向的字符覆盖慢指针指向的字符

#### 代码 ####

class Solution {
        
       public  boolean backspaceCompare(String s,String t){
        
    
             return message(s).equals(message(t));
        }
        /**
         * 写一个方法来看看最终的文本信息
         */
        public  String message(String str){
        
            char[] chars = str.toCharArray();
    
            //如果扫描到#则要把前面一个覆盖
            //快慢指针
            //如果快指针指向的是#，则继续后移，直到找到一个非#
            //如果快指针指向的不是#,则把快指针指向的字符覆盖慢指针指向的字符
            int slow=0;
            int fast;
            for (fast=0;fast<chars.length;fast++){
        
                if (chars[fast]!='#'){
        
    
                  chars[ slow++]=chars[fast];
    
                }else if (chars[fast]=='#'&& slow!=0){
        
                    slow--;
                }
            }
             //返回字符串
            return String.valueOf(chars,0,slow);
        }
    }

[a340207bc99c48538c082364ae189b01.png]: https://img-blog.csdnimg.cn/a340207bc99c48538c082364ae189b01.png
[27.]: https://leetcode.cn/problems/remove-element/
[f0fabd9acb304015afbf5af26fc2efa4.png]: https://img-blog.csdnimg.cn/f0fabd9acb304015afbf5af26fc2efa4.png
[5a05532f6cde442ca8f01d3679d38a9b.png]: https://img-blog.csdnimg.cn/5a05532f6cde442ca8f01d3679d38a9b.png
[324f034df5494b2c9cd7f1a62a867eb7.png]: https://img-blog.csdnimg.cn/324f034df5494b2c9cd7f1a62a867eb7.png
[a6f126625d054eda84aba0b2da26d57b.png]: https://img-blog.csdnimg.cn/a6f126625d054eda84aba0b2da26d57b.png
[23543891f9be42a4a2735ac07c2b02f2.png]: https://img-blog.csdnimg.cn/23543891f9be42a4a2735ac07c2b02f2.png
[Link 1]: https://leetcode.cn/problems/remove-duplicates-from-sorted-array/
[https_leetcode.cn_problems_move-zeroes]: https://leetcode.cn/problems/move-zeroes/
[769ad42caa814b84ba741c04f75df432.png]: https://img-blog.csdnimg.cn/769ad42caa814b84ba741c04f75df432.png
[977.]: https://leetcode.cn/problems/squares-of-a-sorted-array/
[Link 2]: https://leetcode.cn/problems/backspace-string-compare/