【刷题记录】合并两个有序数组、移除元素

简介: 【刷题记录】合并两个有序数组、移除元素

本系列博客为个人刷题思路分享,有需要借鉴即可。

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;
}

完。

相关文章
|
存储
顺序表oj--移除元素&&删除重复项&&合并两个有序数组
顺序表oj--移除元素&&删除重复项&&合并两个有序数组
107 0
|
4月前
|
程序员
【刷题记录】移除链表元素
【刷题记录】移除链表元素
|
4月前
|
Python
【面试题解答】一个有序数组 nums ,原地删除重复出现的元素
【面试题解答】一个有序数组 nums ,原地删除重复出现的元素
40 0
|
7月前
27. 移除元素 88. 合并两个有序数组
27. 移除元素 88. 合并两个有序数组
40 0
|
7月前
|
存储
力扣 合并两个有序数列||移除元素
力扣 合并两个有序数列||移除元素
45 0
删除有序链表中重复的元素-II(链表)
双指针,slow和fast,并且增加标记flag初始为1。
51 0
移除元素、合并两个有序数组(leetcode)
移除元素、合并两个有序数组(leetcode)
|
算法 Go C++
【面试必刷TOP101】 删除有序链表中重复的元素-I & 删除有序链表中重复的元素-II
【面试必刷TOP101】 删除有序链表中重复的元素-I & 删除有序链表中重复的元素-II
53 0
27. 移除元素 26. 删除有序数组中的重复项 88. 合并两个有序数组(双指针遍历)上
27. 移除元素 26. 删除有序数组中的重复项 88. 合并两个有序数组(双指针遍历)上
65 1
每日一题——删除链表中重复的元素——II
每日一题——删除链表中重复的元素——II