1. 題目
1.1 英文題目
Given an integer array nums and an integer val, remove all occurrences of val in nums in-place. The relative order of the elements may be changed.
Since it is impossible to change the length of the array in some languages, you must instead have the result be placed in the first part of the array nums. More formally, if there are k elements after removing the duplicates, then the first k elements of nums should hold the final result. It does not matter what you leave beyond the first k elements.
Return k after placing the final result in the first k slots of nums.
Do not allocate extra space for another array. You must do this by modifying the input array in-place with O(1) extra memory.
1.2 中文題目
給你一個陣列 nums 和一個值 val，你需要 原地 移除所有數值等于 val 的元素，并回傳移除后陣列的新長度，
不要使用額外的陣列空間，你必須僅使用 O(1) 額外空間并 原地 修改輸入陣列，
元素的順序可以改變，你不需要考慮陣列中超出新長度后面的元素，
1.3輸入輸出
| 輸入 | 輸出 |
|---|---|
| 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,4,0,3,,,_] |
2. 實驗平臺
IDE：VS2019
IDE版本：16.10.1
語言：c++11
3. 程式
3.1 測驗程式
#include "Solution.h"
#include <vector> // std::vector
#include<iostream> // std::cout
using namespace std;
// 主程式
void main()
{
// // 輸入
vector<int> nums = { 0,1,2,2,3,0,4,2 };
int val = 2;
Solution solution; // 實體化Solution
int k = solution.removeElement(nums, val); // 主功能
// 輸出
cout << k << ", [";
for (int i = 0; i < k; i++)
{
if (i == k - 1)
cout << nums[i] << "]";
else
cout << nums[i] << ",";
}
}
3.2 功能程式
3.2.1 最佳程式
（1）代碼
#pragma once
#include<vector> // std::vector
using namespace std;
//主功能（快慢指標法，雙指標法）
class Solution
{
public:
int removeElement(vector<int>& nums, int val)
{
int res = 0; // 存盤去重后陣列元素個數
for (int i = 0; i < nums.size(); ++i) // 快指標i遍歷陣列
if (nums[i] != val) // 若快指標指向元素不是目標元素
nums[res++] = nums[i]; // 則慢指標res+1，且慢指標指向快指標當前元素
return res;
}
};
此程式參考：https://www.cnblogs.com/lightwindy/p/8628297.html
（2）解讀
快慢指標對于這種O(1)空間復雜度的陣列問題真的很好用，雖然菜雞的我還沒有掌握它的靈魂，廢話不多說，這個方法用的快慢指標法，也叫雙指標法，res作為慢指標，始終指向的是去重后的陣列元素，而i作為快指標，一馬當先，遍歷整個陣列，如果快指標指向的元素不是目標元素，也就是去重元素，就讓慢指標+1，同時指向該元素，i遍歷一遍，演算法結束，
解讀參考：https://www.cnblogs.com/forPrometheus-jun/p/10889152.html
3.2.2 自寫程式
（1）代碼
#pragma once
#include<vector> // std::vector
using namespace std;
//主功能
class Solution
{
public:
int removeElement(vector<int>& nums, int val)
{
while(1)
{
vector<int>::iterator iter = find(nums.begin(), nums.end(), val); // 在陣列中找到目標元素
if (iter != nums.end()) // 若找到
nums.erase(iter); // 則洗掉該元素
else // 若找不到，即陣列中不存在該目標元素，則不再查找
break;
}
return nums.size();
}
};
（2）思路
菜雞的我只想到暴力演算法，遍歷整個陣列，遇到去重元素，就洗掉該元素，遍歷完后，回傳去重后陣列長度即可，
從前往后遍歷，如果發現有元素重復，則將重復元素剔除
4. 相關知識
（1） 快慢指標（Fast-Slow Pointer）
關于快慢指標，Leetcode的26題也用到了該演算法，這個演算法真不錯，26題的該演算法解法可以參考：https://www.cnblogs.com/yunmeng-shi/p/14927735.html
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/288414.html
標籤：C++