补充.顺序表的一个好玩细节
注：下面的是任意位置插入的正确代码
SeqList Sq; //相关代码 void SeqListInsert(SeqList* ps, size_t pos, int e)//优美点2 { assert(ps); assert(pos <= ps->size);//优美点1 int end = ps->size-1;//优美点2 while (end >= (int)pos)//优美点2 { ps->a[end + 1] = ps->a[end]; --end; } ps->a[pos] = e; ps->size++; }
关于上面的代码我想补充三个点：
这个函数名之所以没有加before和after，而是直接是Insert，是为了跟着STL库走
库里的函数的参数pos位的参数类型就是size_t，所以没有写成int类型
顺序表/数组中的涉及到/提到的位置都是下标
但是这里的参数类型为size_t就给后面while循环带来了一些问题：
//错误示范1 void SeqListInsert(SeqList* ps, size_t pos, int e) { assert(ps); assert(pos < ps->size); size_t end = ps->size-1; while (end >= pos)//end为size_t类型时，，如果题目pos给0的话 //end (-1)就会转换成一个非常大的数，造成死循环 { ps->a[end + 1] = ps->a[end]; --end; } ps->a[pos] = e; ps->size++; } //错误示范2 void SeqListInsert(SeqList* ps, size_t pos, int e) { assert(ps); assert(pos < ps->size); int end = ps->size-1;//将end改为int后，在while(int和size_t类型比较的时候) //如果题目pos给0的话 //end为-1的时候也会变成size_t，向上提升，造成死循环 while (end >= pos) { ps->a[end + 1] = ps->a[end]; --end; } ps->a[pos] = e; ps->size++; } //正确做法：在函数内部将pos位置强制转换为int类型，进行比较
题目1：移除链表元素：
要求：时间复杂度O(N),空间复杂度O(1)
整体思路：
双指针法：用src找到值不为val的数组元素，dest记录新数组的元素个数
特点：
当数组元素值为val的时候，dest和src拉开距离
当数组元素值不为val的时候，dest和src距离保持不变
代码：
int removeElement(int* nums, int numsSize, int val){ int dest=0; int src=0; while(src<numsSize) { if(nums[src]==val) { ++src; } else { nums[dest]=nums[src]; ++dest; ++src; } } return dest; }
或者：
int removeElement(int* nums, int numsSize, int val){ if(nums==NULL||numsSize==0) return 0; int j=0; for(int i=0;i<numsSize;i++) { if(nums[i]!=val) { nums[j++]=nums[i]; } } return j; }
题目2：删除有序数组中的重复项
int removeDuplicates(int* nums, int numsSize){ int dest=0; int src=0; while(src<numsSize) { if(nums[dest]==nums[src]) { src++; } else { nums[++dest]=nums[src]; src++; } } return dest+1; }
或者
int removeDuplicates(int* nums, int numsSize){ int j=0; for(int i=0;i<numsSize;i++) { if(nums[j]!=nums[i]) { nums[++j]=nums[i]; } } return j+1; }
第一题的移除元素时将所有值为val的数组元素全部移除，而本题是重复的元素移除到只剩一个
备注：上面两题非常的相似，建议举一个222223的例子通过两个指针dest 和src指针去画图演示一下，了解一下图示和代码上的异同点.
题目3：合并两个有序数组
题目描述： 比如：nums1={1,2,5,31,32} nums2={12,45} 题目给出数组nums1已经使用的长度为m,总长度为nums1Size=m+n，注，这里m<=nums1Size 数组nums2已经使用的长度为n,总长度为numsSize,注，这里n==nums2Size nums1的总容量nums1Size就是m+n,题目想通过将num2数组里的数据加进num1中，并使得合并后依旧有序 //常规思路： 思路1：先将nums2的内容无脑加进nums1已有元素的后面,然后通过排序使得新的nums1有序 //缺点：时间复杂度高 思路2：开辟一个长度为numsSize（也就是m+n）,然后然后从前往后，不断选小尾插到开辟的数组中 //缺点：返回使就会被题目限制,题目要求只需要将数据给到nums1就可以了 正确做法：nums1和nums2从后往前不断选大,放到nums1的后面（往前） void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n)
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n){ int end1=m-1; int end2=n-1; int i=m+n-1; while(end1>=0&&end2>=0) { if(nums1[end1]>nums2[end2]) { nums1[i]=nums1[end1]; --end1; --i; } else { nums1[i]=nums2[end2]; --end2; --i; } } while(end2>=0) { nums1[i]=nums2[end2]; --end2; --i; } }
这样比较然后插入，nums1和nums2数组肯定有一个数组会先到0
这里的循环条件不能改成i>=0，因为肯定会有一个数组会先到0，就会数组下标越界
