本系列博客为个人刷题思路分享,有需要借鉴即可。
1.题目链接:
T1:LINK
T2:LINK
2.详解思路:
T1:
思路1:弄个新数组,比较两个数组中的值,哪个小就把哪个值放到新数组中。
分析1:时间复杂度:O(N);空间复杂度:O(N)
但是显然在本题中题目明确表示要放在原数组中,否定该思路。
思路2:把nums2内容拷贝到nums1有效数据的后面,再进行排序
分析2:否定,仅排序而言时间复杂度:O(N*logN)
思路3:造三个指针,倒序条件赋值
分析3:时间复杂度O(N) 空间复杂度O(1) so:优秀算法
代码如下:
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {int end1 = m - 1;int end2 = n - 1;int end = m + n - 1;//开始赋值while(end1>=0&&end2>=0){if(nums1[end1]>nums2[end2]){nums1[end--] = nums1[end1--];}else{nums1[end--] = nums2[end2--];}}//当end1或者end2小于0了就跳出循环了,就会出现两种局面//局面1:end1为0但是end2不为0,这时候只需要把nums2中剩下的数据搬到nums1即可if(end1<0&&end2>=0){int i = 0;for(i = end2;i>=0;i--){nums1[end--] = nums2[i];}}//局面2:end1不为0但是end2为0,那就不用管了,刚好满足题目}
T2:
思路1:创建一个新数组,原来数组不是我们要移除的元素的我们就拷贝到新数组中即可。
分析1:题目要求原地删除,该做法不满足题意
思路2:我们在原数组中,找到一个要删除的数字我就把他后面的所有元素都往前挪动一位
分析2:否定,时间复杂度O(N*N)
思路3:造两个指针,一个指针记录有效的数字个数,另一个指针在前面探路
分析3:时间复杂度:O(N)优秀思路!
代码实现:
int removeElement(int* nums, int numsSize, int val) {int i = 0;int p1 = 0;//探路者int p2 = 0;//守家者for(i = 0;i<numsSize;i++){if(nums[p1]==val){p1++;}else{nums[p2++] = nums[p1++];}}return p2;
}
完。