数组的内存是连续的数组的优点有三点下标访问时间复杂度是O1末尾位置增加删除时间复杂度是O1访问元素前后相邻位置的元素非常方便缺点非末尾位置增加删除元素需要进行大量的数据移动O(n)数组扩容消耗较大搜索的时间复杂度无序数组-线性搜索On) 有序数组-二分搜索Ologn定义一个数组int arr[10]; 数组存放数据类型 数组名[数组大小]数组的索引是从零开始的如果数组的大小是10访问的是arr[10]就会造成越界访问。查找是arr[3],而搜索是for(int i0;in;i){ if(arr[i]val){ ………… } }数组名代表了数组第一个元素的指针可以通过指针去访问数组元素。用代码实现数组包装#includeiostream #includestdlib.h #includetime.h using namespace std; //动态扩容的数组,在堆上进行创建数据 templateclass T class Array { private: T* mpArr; int mCap; int mCur; //内部扩容函数 void expand(int size) { T* p new T[size]; memcpy(p, mpArr, sizeof(T) * mCap); delete[]mpArr; mpArr p; mCap size; } public: Array(int size 10) :mCur(0), mCap(size) { mpArr new T[mCap](); } ~Array() { delete[]mpArr; //防止指针为也指针 mpArr nullptr; } void push_back(T val) { if (mCur mCap) { expand(2 * mCap); } mpArr[mCur] val; } void pop_bash() { if (mCur 0) { return; } mCur--; } void insert(int pos, T val) { if (pos0 || posmCur) { throwpos invalid!; } if (mCur mCap) { expand(2 * mCap); } for (int i mCur-1; i pos; i--) { mpArr[i 1] mpArr[i]; } mpArr[pos] val; mCur; } void erase(int pos) { if (pos0 || posmCur) { throwpos invalid!; } for (int i pos 1; i mCur; i) { mpArr[i - 1] mpArr[i]; } mCur--; } int find(T val) { for (int i 0; i mCur; i) { if (mpArr[i] val) { return i; } } return -1; } void change(int pos, T val) { if (pos0 || posmCur) { throwpos invalid!; } mpArr[pos] val; } void show() const{ for (int i 0; i mCur; i) { cout mpArr[i] ; } cout endl; } }; int main() { Arrayint arr; srand(time(0)); for (int i 0; i 10; i) { arr.push_back(rand() % 100); } arr.show(); arr.pop_bash(); arr.show(); arr.insert(0, 100); arr.show(); arr.insert(10, 130); arr.show(); int pos arr.find(100); if (pos ! -1) { arr.erase(pos); arr.show(); } return 0; }一、设计思路1. 为什么需要动态扩容数组静态数组大小固定无法在运行时改变长度。动态扩容数组能在空间不足时自动扩大既保留了数组随机访问的高效性又避免了手动管理内存的麻烦。本类的核心思想是在堆上分配连续内存new T[size]。用mCap记录总容量mCur记录当前已存储元素个数。当push_back或insert时若容量已满调用内部expand函数翻倍扩容并将旧数据拷贝到新空间后释放旧空间。2. 提供的接口构造/析构初始化容量默认10释放内存。push_back尾插必要时扩容。pop_bash尾删实际应为pop_back命名拼写错误。insert在指定位置插入元素后续元素后移。erase删除指定位置元素后续元素前移。find顺序查找值返回第一个匹配的下标否则返回 -1。change修改指定位置的元素。show打印当前所有元素。这些接口覆盖了基本增删改查体现了数组型容器的常见功能。二、代码详解1. 成员变量与构造/析构private: T* mpArr; // 指向堆上数组的指针 int mCap; // 总容量 int mCur; // 当前元素个数 public: Array(int size 10) : mCur(0), mCap(size) { mpArr new T[mCap](); // 加()进行值初始化对基本类型置零 } ~Array() { delete[] mpArr; mpArr nullptr; // 防止野指针 }构造函数允许指定初始容量默认10。new T[mCap]()末尾的()会对每个元素进行值初始化如int初值为 0避免未初始化的垃圾值。析构时释放数组并将指针置空这是一个好习惯。2. 内部扩容函数expandvoid expand(int size) { T* p new T[size]; memcpy(p, mpArr, sizeof(T) * mCap); delete[] mpArr; mpArr p; mCap size; }明显的 bugint* p new T[size];类型写死为int*应当改为T* p new T[size];否则对于非int类型会编译错误或行为异常。潜在问题memcpy按字节拷贝对T是复杂对象含指针、虚函数、非平凡拷贝构造等时会引发浅拷贝、资源泄漏甚至崩溃。应使用std::copy或手动循环赋值并调用拷贝构造函数。扩容策略翻倍 (2 * mCap)均摊时间复杂度为 O(1)是常用策略。3. 尾插push_back和尾删pop_bashvoid push_back(T val) { if (mCur mCap) expand(2 * mCap); mpArr[mCur] val; } void pop_bash() { if (mCur 0) return; mCur--; }push_back先判断是否需要扩容然后在mCur位置存入新值并让mCur自增。pop_bash实际应为pop_back只简单减少mCur逻辑上“删除”了尾部元素但并未析构对象。对于复杂类型应在减少计数前显式调用析构函数mpArr[--mCur].~T();。当前代码对int没问题但作为模板不够通用。4. 插入insert和 删除erasevoid insert(int pos, T val) { if (pos 0 || pos mCur) throw pos invalid!; if (mCur mCap) expand(2 * mCap); for (int i mCur - 1; i pos; i--) mpArr[i 1] mpArr[i]; mpArr[pos] val; mCur; } void erase(int pos) { if (pos 0 || pos mCur) throw pos invalid!; for (int i pos 1; i mCur; i) mpArr[i - 1] mpArr[i]; mCur--; }插入位置允许[0, mCur]即允许在末尾插入等同于push_back。元素移动时采用从后往前遍历避免覆盖未移动的数据正确。erase的边界检查应该用pos 0 || pos mCur否则会允许删除mCur位置无效位置导致逻辑错误。同样对于复杂对象移动时应使用移动赋值尾部删除时要调用析构。5. 查找find和修改changeint find(T val) { for (int i 0; i mCur; i) if (mpArr[i] val) return i; return -1; } void change(int pos, T val) { if (pos 0 || pos mCur) throw pos invalid!; mpArr[pos] val; }find返回类型应为int下标却声明为T。当T是int时恰好能工作但若T是double等返回-1进行隐式转换且语义不正确。应当改为int find(const T val) const。change边界检查正确pos mCur。6. 打印showvoid show() const { for (int i 0; i mCur; i) cout mpArr[i] ; cout endl; }标记为const成员函数不会修改对象设计正确。双指针实现数组逆序用两指针去实现一个数组的逆序用第一个指针指向数组第一个元素第二个指针指向最后一个元素交换两个指针指向的内容然后将指针位置进行移动直到第一个指针大于或等于第二个指针。代码实现//用双指针的思想实现逆序 #includeiostream using namespace std; #includestring void reverse(char arr[], int size) { char* p arr; char* q arr size - 1; while (p q) { char ch *p; *p *q; *q ch; p; q--; } } int main() { char arr[] hello world; reverse(arr, strlen(arr)); cout arr; return 0; }双指针实现满足条件数据交换将偶数放在数组左侧同样第一个指针指向数组第一个元素第二个指针指向最后一个元素当左指针找到偶数的时候向右移动找到奇数的时候等待右指针找到偶数同样的思路让右指针找到偶数然后交换左右两个指针。同样如果是其他的条件可以判断条件直接进行交换即可大体思路应是相同的//将偶数放在数组的左侧 #includeiostream using namespace std; #includestdlib.h #includetime.h void AdjustArray(int arr[],int size) { int* p arr; int* q arr size - 1; while (p q) { while (p q) { if ((*p 0x1) 1) { break; } p; } while (p q) { if ((*q 0x1) 0) { break; } q--; } if (p q) { int temp *p; *p *q; *q temp; } } } int main() { srand(time(0)); int arr[10] { 0 }; for (int i 0; i 10; i) { arr[i] rand() % 100; } for (int v : arr) { cout v ; } cout endl; AdjustArray(arr, 10); for (int v : arr) { cout v ; } return 0; }双指针实现数组元素个数查询给你一个数组 nums 和一个值 val你需要 原地 移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。假设 nums 中不等于 val 的元素数量为 k要通过此题您需要执行以下操作• 更改 nums 数组使 nums 的前 k 个元素包含不等于 val 的元素。nums 的其余元素和 nums 的大小并不重要。• 返回 k。用户评测评测机将使用以下代码测试您的解决方案int[] nums [...]; // 输入数组 int val ...; // 要移除的值 int[] expectedNums [...]; // 长度正确的预期答案。 // 它以不等于 val 的值排序。 int k removeElement(nums, val); // 调用你的实现 assert k expectedNums.length; sort(nums, 0, k); // 排序 nums 的前 k 个元素 for (int i 0; i k; i) { assert nums[i] expectedNums[i]; }如果所有的断言都通过你的解决方案将会 通过。示例 1输入nums [3,2,2,3], val 3 输出2, nums [2,2,_,_]解释你的函数应该返回 k 2, 并且 nums 中的前两个元素均为 2。你在返回的 k 个元素之外留下了什么并不重要因此它们并不计入评测。示例 2输入nums [0,1,2,2,3,0,4,2], val 2 输出5, nums [0,1,4,0,3,_,_,_]解释你的函数应该返回 k 5并且 nums 中的前五个元素为 0,0,1,3,4。注意这五个元素可以任意顺序返回。你在返回的 k 个元素之外留下了什么并不重要因此它们并不计入评测。提示• 0 nums.length 100• 0 nums[i] 50• 0 val 100代码实现class Solution { public: int removeElement(vectorint nums, int val) { int n nums.size(); if(n0)return 0; int *p nums.data(); int *q nums.data() n - 1; while (p q) { if (*q val) { q--; continue; } if (*p val) { *p *q; q--; } else { p; } } return p - nums.data(); } };1. 函数声明int removeElement(vectorint nums, int val)功能从数组nums中移除所有值等于val的元素并返回新数组的长度nums的前k个位置存放结果顺序无关。参数整数向量nums引用传递原地修改、目标值val。返回值移除后剩余元素的个数。2. 变量定义int n nums.size(); if(n0) return 0;获取数组长度若为空则直接返回0。int *p nums.data(); int *q nums.data() n - 1;nums.data()返回指向数组首元素的指针。p指向数组开头头指针q指向数组末尾尾指针。该实现意图使用双指针两端逼近的方式将等于val的元素用尾部非val的元素覆盖从而减少数组长度。3. 主循环while (p q) { if (*q val) // ① { q--; continue; } if (*p val) // ② { *p *q; q--; } else // ③ { p; } }循环条件p q表示指针尚未交错仍有元素待处理。分支①*q val如果尾指针指向的元素等于val则该元素最终应被丢弃直接向左移动qq--跳过它。使用continue跳过本轮后续检查继续下一次循环。分支②*p val且此时*q ! val头指针指向的值等于val需要用尾部有效值覆盖它。将*q的值赋给*p然后q--这个尾部元素已被使用删除它。注意p没有移动因为新覆盖过来的值也可能等于val需要下一轮重新检查。分支③*p ! val且*q ! val头指针指向的值不是val是有效值保留它p继续检查下一个位置。4. 返回新长度return p - nums.data();循环结束时p指向第一个未处理的位置也就是新数组的结束位置。指针相减得到从数组起始到p的元素个数即剩余有效元素的个数。5. 算法意图分析该方法试图通过从两端向中间扫描将等于val的元素替换为右侧非val的元素从而缩小数组范围。时间复杂度O(n)每个元素最多被访问一次。空间复杂度O(1)仅使用指针变量。6. 总结原代码的核心思想是双指针覆盖但实现细节有误无法通过标准测试用例。作为学习材料它展示了指针运算的灵活性和容易出错的边界条件。在实际刷题或工程中建议采用快慢指针或更清晰的索引版本既简单又可靠。希望这份详解对你有所帮助如有疑问欢迎继续交流。