IT评测·应用市场-qidao123.com技术社区

标题: 【代码随想录】移除数组 [打印本页]

---

作者: 宝塔山    时间: 2024-8-7 07:50
标题: 【代码随想录】移除数组
本文为《代码随想录》的学习笔记，原文链接：代码随想录

题目

原题链接：
27. 移除元素
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值即是 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。
假设 nums 中不即是 val 的元素数量为 k，要通过此题，您需要执行以下操纵：

• 更改 nums 数组，使 nums 的前 k 个元素包含不即是 val 的元素。nums 的其余元素和 nums 的巨细并不紧张。
  
• 返回 k。
  

示例 1：

1. <strong>输入：</strong>nums = [3,2,2,3], val = 3
2. <strong>输出：</strong>2, nums = [2,2,_,_]
3. <strong>解释：</strong>你的函数函数应该返回 k = 2, 并且 nums<em> </em>中的前两个元素均为 2。
4. 你在返回的 k 个元素之外留下了什么并不重要（因此它们并不计入评测）。

复制代码

示例 2：

1. <strong>输入：</strong>nums = [0,1,2,2,3,0,4,2], val = 2
2. <strong>输出：</strong>5, nums = [0,1,4,0,3,_,_,_]
3. <strong>解释：</strong>你的函数应该返回 k = 5，并且 nums 中的前五个元素为 0,0,1,3,4。
4. 注意这五个元素可以任意顺序返回。
5. 你在返回的 k 个元素之外留下了什么并不重要（因此它们并不计入评测）。

复制代码

提示：

• 0 <= nums.length <= 100
  
• 0 <= nums <= 50
  
• 0 <= val <= 100
  

题解

为适应机试情况，使用Dev C++编译
输入说明：n=数组元素个数，nums数组元素，一个值val
输出说明：不即是 val 的元素数量为 k，nums的剩余元素
示例一：
   输入：4 3 2 2 3 3
  输出：
  2
  2 2
  示例二：
   输入：8 0 1 2 2 3 0 4 2 2
  输出：
  5
0 1 3 0 4
  方法一：使用erase() 函数

erase() 说明
erase可以删去容器中指定位置的元素，容器的size（巨细）会改变，但是容器的容量稳定。

1. //删除a向量中全部元素
2. a.erase(a.begin(), a.end());
4. //删除a向量中下标0-2共三个元素
5. a.erase(a.begin(), a.begin()+3);

复制代码

测试程序：

1. int main(){
2.     for(int i = 1; i < 5; i++) a.push_back(i); //输入数据
3.     cout << "使用erase删除前：" ;
4.     for(int i = 0; i < a.size(); i++){
5.         cout << a[i] << " ";
6.     }
7.     cout << endl;
8.     a.erase(a.begin(), a.begin() + 3);
9.     cout << "使用erase删除后：";
10.     for(int i = 0; i < a.size(); i++){
11.         cout << a[i] << " ";
12.     }
13.     return 0;
14. }
16. //输出：
17. 使用erase删除前：1 2 3 4 5
18. 使用erase删除后：4 5

复制代码

留意：erase删除nums中元素后，由于后面的元素均向前移动了一个位置，因此需要i--使指针指向原来的i-1元素，如许在下一轮遍历时指针才会指向原来的i+1元素，否则会出现遗漏。
使用Dev C++编译

1. #include <bits/stdc++.h>
2. using namespace std;
3. vector<int>nums;
4. int removeElement(vector<int>& nums, int val)
5. {
6.        
7.     int k=0;
8.         int length=nums.size();
9.         for(int i=0;i<length;i++)
10.         {
11.                 if(nums[i]==val)
12.                 {
13.                         nums.erase(nums.begin()+i);
14.                         i--;//erase数组中的i元素后，后面的元素均向前移了一位，因此需要i--，指针指向原来i-1元素
15.                         length--;//erase删去一个元素,length减一
16.                 }
17.         }
18.         k=nums.size();
20.     return k;
21.        
22. }
23. int main()
24. {
25.         int n,val;       
26.         cin>>n;
27.         for(int i=0;i<n;i++)
28.         {
29.                 int ans;
30.                 cin>>ans;
31.                 nums.push_back(ans);
32.         }
33.         cin>>val;
34.        
35.         int k = removeElement(nums, val); // 调用你的实现
36.         cout<<k<<endl;
37.         for(int i=0;i<k;i++)
38.         {
39.                 cout<<nums[i]<<" ";
40.         }
41.         return 0;
42. }

复制代码

 在LeetCode中运行

1. class Solution {
2. public:
3.     int removeElement(vector<int>& nums, int val) {
4.         int k = 0;
5.         int length = nums.size();
6.         for (int i = 0; i < length; i++) {
7.             if (nums[i] == val) {
8.                 nums.erase(nums.begin() + i, nums.begin() + i + 1);
9.                 i--;
10.                 length--;
11.             }
12.         }
13.         k = nums.size();
15.         return k;
16.     }
17. };

复制代码

时间复杂度：O(n^2)
erase()方法的时间复杂度为O(n)
空间复杂度：O(1)
方法二：暴力解法

本质上头脑与前一种雷同。
这个题目暴力的解法就是两层for循环，一个for循环遍历数组元素 ，第二个for循环更新数组。
在LeetCode中运行

1. // 时间复杂度：O(n^2)
2. // 空间复杂度：O(1)
3. class Solution {
4. public:
5.     int removeElement(vector<int>& nums, int val) {
6.         int size = nums.size();
7.         for (int i = 0; i < size; i++) {
8.             if (nums[i] == val) { // 发现需要移除的元素，就将数组集体向前移动一位
9.                 for (int j = i + 1; j < size; j++) {
10.                     nums[j - 1] = nums[j];
11.                 }
12.                 i--; // 因为下标i以后的数值都向前移动了一位，所以i也向前移动一位
13.                 size--; // 此时数组的大小-1
14.             }
15.         }
16.         return size;
18.     }
19. };

复制代码

 

• 时间复杂度：O(n^2)
  
• 空间复杂度：O(1)
  

方法三：双指针法

双指针法（快慢指针法）：通过一个快指针和满指针在一个for循环下完成两个for循环的工作。
定义快慢指针

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

在编写代码时需留意i++与++i的区别：
通俗地讲，i++是先赋值再自增，++i是先自增再赋值
在LeetCode中运行

2. class Solution {
3. public:
4.     int removeElement(vector<int>& nums, int val) {
5.         int slowIndex = 0;
6.         int length = nums.size();
7.         for (int fastIndex = 0; fastIndex < length; fastIndex++) {
8.             if (nums[fastIndex] != val) {
9.                 nums[slowIndex++] = nums[fastIndex];
10. //相当于
11. //nums[slowIndex]=nums[fastIndex];
12. //slowIndex++;
13.             }
14.         }
15.         return slowIndex;
16.     }
17. };

复制代码

留意这些实现方法并没有改变元素的相对位置！

• 时间复杂度：O(n)
  
• 空间复杂度：O(1)
  

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。

---

欢迎光临 IT评测·应用市场-qidao123.com技术社区 (https://dis.qidao123.com/)

Powered by Discuz! X3.4