烟台定制网站建设电话,wordpress+最新版本,wordpress网站支持中文注册,中国建筑股份有限公司 官网移除元素 此题简单#xff0c;用双指针方法即可#xff0c; 如果右指针指向的元素不等于val#xff0c;它一定是输出数组的一个元素#xff0c;我们就将右指针指向的元素复制到左指针位置#xff0c;然后将左右指针同时右移#xff1b; 如果右指针指向的元素等于 val用双指针方法即可 如果右指针指向的元素不等于val它一定是输出数组的一个元素我们就将右指针指向的元素复制到左指针位置然后将左右指针同时右移 如果右指针指向的元素等于 val它不能在输出数组里此时左指针不动右指针右移一位。
且最后需要输出的数组长度就是left的值。不多说上代码
int removeElement(int* nums, int numsSize, int val)
{int left 0;int right 0;for(int i 0;inumsSize;i){if(nums[right] ! val){nums[left]nums[right];left;right;}else{right;}}return left;}时间复杂度O(N) 空间复杂度O(1)
删除有序数组中的重复项 暴力想法
注意是暴力想法不是暴力解法 作为直男直接就是想实现。 直接遍历看题目是已经确定了是有序的遇到与上一个不相等的直接给他拿到新的数组里面存起来。遍历完直接新数组就是答案。 看样子是很接近了哈毕竟属于简单的题目。但是 O(1) 额外空间的条件下完成这个是我们跨不过去的坎。既然如此那就得考虑在原数组上操作。
双指针法
定义两个指针fast 和 slow 分别为快指针和慢指针快指针表示遍历数组到达的下标位置慢指针表示下一个不同元素要填入的下标位置初始时两个指针都指向下标 1。 假设数组nums 的长度为 n。将快指针 fast 依次遍历从 1 到 n-1 的每个位置对于每个位置如果nums[fast] !nums[fast-1],说明 nums[fast] 和之前的元素都不同因此将 nums[fast] 的值复制到nums[slow]然后将 slow 的值加 1即指向下一个位置。遍历结束之后从 nums[0] 到 nums[slow−1] 的每个元素都不相同且包含原数组中的每个不同的元素因此新的长度即为 slow返回 slow 即可。
//C
int removeDuplicates(int* nums, int numsSize)
{int right 1;int left 1;for(int i1;inumsSize;i){if(nums[right-1]!nums[right]){nums[left]nums[right];left;right;}else{right;}}return left;
}合并两个有序数组 方法一直接合并后排序
最直观的方法是先将数组 nums 2放进数组nums 1的尾部然后直接对整个数组进行排序。
int cmp(int* a, int* b) {return *a - *b;
}
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {for (int i 0; i ! n; i) {nums1[m i] nums2[i];}qsort(nums1, nums1Size, sizeof(int), cmp);
}时间复杂度O((mn)\log(mn)) 空间复杂度O(log(mn))
方法二逆向双指针
观察可知nums 1 的后半部分是空的可以直接覆盖而不会影响结果。因此可以指针设置为从后向前遍历每次取两者之中的较大者放进 nums 1的最后面。
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n)
{int end1 m-1;int end2 n -1;int end mn-1;while(end1 0 end2 0){if(nums1[end1]nums2[end2]){nums1[end--]nums1[end1--];}else{nums1[end--]nums2[end2--];}}while(end2 0){nums1[end--] nums2[end2--];}}时间复杂度O(mn) 空间复杂度O(1)
